Giải bài trực tuyến

Năm 2020, cờ vua là môn thể thao trí tuệ phổ biến nhất trên toàn thế giới, vượt xa cờ tướng. Ở trường chuyên X, ban giám hiệu muốn học sinh rèn luyện trí óc ngay cả trong giờ thể dục nên đã thay tất cả các môn bóng đá, cầu lông, bóng bàn, … bằng cờ vua. Đăng rất thích đánh cờ vua nên điều này làm cậu hào hứng.

Một bàn cờ vua là một bảng ô vuông mà trên mỗi hàng, mỗi cột các ô màu đen và trắng nằm xen kẽ nhau.Trên thị trường, ngoài bàn cờ vua truyền thống loại 1(kích thước 8x8, 2 ô ở 2 góc đối diện có màu giống nhau) còn có bán 2 loại bàn cờ vua mới : loại 2 (kích thước 9x9, 4 ô ở 4 góc màu đen) và loại 3 (kích thước 9x9, 4 ô ở 4 góc màu trắng).

Trong một lần làm bài tập tin học, Đăng bắt gặp một bảng kích thước NxN chỉ gồm các ô có giá trị 0 và 1. Xem như các ô 0 có màu trắng và các ô 1 có màu đen. Ta định nghĩa một hình vuông loại A là hình vuông có tính chất giống bàn cờ loại A (ở đây chỉ quan tâm đến tính xen kẽ màu của các ô liên tiếp và màu của 4 ô ở 4 góc chứ không tính đến kích thước). Một ô ‘1’ được xem như một hình vuông loại 2 và một ô ‘0’ được xem như một hình vuông loại 3.

Gọi S_A là độ dài cạnh của hình vuông loại A lớn nhất  và T_A là số lượng hình vuông loại A có độ dài cạnh bằng S_A.Đăng muốn biết giá trị của các S_i và T_i.

Input

	Dòng đầu là số nguyên dương N (N <= 2000).
	N dòng tiếp theo, mỗi dòng gồm N kí tự là ‘0’hoặc ‘1’ 

Output

Gồm 3 dòng, trên dòng thứ i ghi 2 số nguyên S_i và T_i.
Nếu không tồn tại hình vuông loại A thì xem như S_A=T_A=0.

Example

Input:
5
00101
11010
00101
01010
11101

Output:
4 1
3 3
3 2