Mr. Zhang is teaching a class about symmetry patterns in squares. For simplicity, he represents a square pattern using a $0-1$ matrix, where the square is decomposed into an $n \times n$ grid, with $0$ representing a white cell and $1$ representing a black cell.

The first topic is axial symmetry, which is easy to identify. A square has $4$ axes of symmetry: the horizontal midline, the vertical midline, and the two diagonals. If a square pattern remains unchanged after a reflection transformation across an axis of symmetry, it is called an axially symmetric pattern. For example, the two patterns below are both axially symmetric.

100    010
100    101
111    000

Mr. Zhang continues to explain rotational symmetry in squares. If a square pattern remains unchanged after a $180^\circ$ rotation about its center, it is called a $180^\circ$ symmetric pattern. If it remains unchanged after a $90^\circ$ clockwise rotation about its center, it is called a $90^\circ$ symmetric pattern. For example, the pattern on the left below is a $180^\circ$ symmetric pattern, and the one on the right is a $90^\circ$ symmetric pattern.

0011    1011
1110    1110
0111    0111
1100    1101

Mr. Zhang continues, saying that if a square pattern has two mutually perpendicular axes of symmetry, it is called a $4$-symmetric pattern; if it is symmetric about all $4$ axes of symmetry, it is called an $8$-symmetric pattern. By definition, a $90^\circ$ symmetric pattern is also a $180^\circ$ symmetric pattern, and an $8$-symmetric pattern is also a $4$-symmetric pattern. When the side length of a square pattern is even, the center of the pattern is the common vertex of the $4$ central cells. When the side length is odd, the pattern has a central cell, and the center of the pattern is the center of this central cell. A pattern with a side length of $1$ is obviously an $8$-symmetric pattern.

Mr. Zhang proved two theorems for the students: Theorem 1: A square pattern is a $4$-symmetric pattern if and only if it is a $180^\circ$ symmetric pattern and an axially symmetric pattern. Theorem 2: A square pattern is an $8$-symmetric pattern if and only if it is a $90^\circ$ symmetric pattern and an axially symmetric pattern.

Finally, it is practice time. Mr. Zhang asks the students to find various symmetric patterns that appear within a large square pattern. Please write a program to implement this requirement. Given a $0-1$ matrix, output the side length of the largest sub-square pattern that satisfies the $8$-symmetric, $90^\circ$ symmetric, $4$-symmetric, $180^\circ$ symmetric, and axially symmetric properties. A sub-square pattern refers to a sub-matrix formed by selecting a set of adjacent rows and columns, representing a small pattern appearing within the large pattern.

Input

The first line of the input is a positive integer $n$, representing the side length of the large square pattern. This is followed by $n$ lines, each containing a $01$ string of length $n$.

Output

Output a single line containing $5$ natural numbers separated by spaces, representing the side lengths of the largest $8$-symmetric, $90^\circ$ symmetric, $4$-symmetric, $180^\circ$ symmetric, and axially symmetric sub-square patterns found in the input, respectively.

Examples

Input 1

5
11100
11000
10111
11000
11100

Output 1

2 2 3 3 5

Note 1

The large pattern has a horizontal axis of symmetry, there is a $2 \times 2$ $8$-symmetric pattern in the top-left corner, and the intersection of the middle $3$ rows and the rightmost $3$ columns forms a $4$-symmetric pattern.

Constraints

$30\%$ of the data satisfies: $5 \le n \le 30$ $60\%$ of the data satisfies: $5 \le n \le 100$ $100\%$ of the data satisfies: $5 \le n \le 500$