C. Hacking the Matrix
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Cláudia is an outstanding researcher and is always looking for new challenges. Thus, she decides to attack the root of all evil in society: the Matrix.

The Matrix can be seen as an $$$N \times N$$$ binary grid, that is, a table with $$$N$$$ rows and $$$N$$$ columns consisting only of $$$0$$$s and $$$1$$$s.

With all her knowledge, Cláudia can perform two operations on the Matrix:

  1. Choose two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le N$$$ and $$$i \ne j$$$) and swap column $$$i$$$ with column $$$j$$$ of the grid, that is, for all $$$1 \le k \le N$$$, swap the positions $$$(k, i)$$$ and $$$(k, j)$$$ of the grid;
  2. Choose two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le N$$$ and $$$i \ne j$$$) and swap row $$$i$$$ with row $$$j$$$ of the grid, that is, for all $$$1 \le k \le N$$$, swap the positions $$$(i, k)$$$ and $$$(j, k)$$$ of the grid;

Thus, to demonstrate her dominance over the Matrix, Cláudia decides to form a C (for Cláudia) in the cells of the Matrix made up of $$$1$$$s. We say that a C of size $$$x$$$ made up of $$$1$$$s exists in the grid if, for a pair of integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le N$$$), the positions $$$(a + i, b)$$$, $$$(a, b + i)$$$, and $$$(a + x, b + i)$$$ of the grid contain $$$1$$$s for all $$$0 \le i \le x - 1$$$.

Help Cláudia by telling, for a given configuration of the Matrix, what is the largest C she can form using the operations at her disposal.

Due to the time limit of the problem, it is important to submit Python solutions using the PyPy3 compiler.

Input

The first line of the input contains an integer $$$N$$$ ($$$1 \le N \le 500$$$).

There will be $$$N$$$ following lines, where the $$$i$$$-th ($$$1 \le i \le N$$$) contains $$$N$$$ integers, where the $$$j$$$-th ($$$1 \le j \le N$$$) is the value $$$a_{i,j}$$$ ($$$0 \le a_{i,j} \le 1$$$) at position $$$(i, j)$$$ of the Matrix grid.

Output

Print a single integer — the side length of the largest C made up of $$$1$$$s that can be formed by performing any number of operations.

Examples
Input
4
0111
1001
0111
0010
Output
3
Input
5
01101
11001
01111
11101
00010
Output
3
Input
3
000
100
000
Output
1
Note

Explanation of the first example: by swapping the second and fourth columns, we get the following configuration of the Matrix:

0111

0100

0111

0010

The underlined part shows the C of size $$$3$$$ that is formed in the grid after this operation. It can be shown that it is not possible to form a larger C in this case.