In the universe, there exists a magical land full of nerds called DMOJistan. The Nerds of DMOJistan are massive fans of the game "Genshin Impact". Nerds specifically enjoy playing with one character: Hu-Tao. Nerds enjoy playing Hu-Tao so much, that in the name of Hu-Tao, the Nerds decided to create a fractal in her name: the so-called Hu-Tao Fractal.

"A fractal is defined as a never-ending pattern, which continually repeats itself"

The smallest Hu-Tao Fractal looks like the pattern below.

1 1 1
1 0 1
1 1 1

A bigger Hu-Tao Fractal would be 3 times larger, and where there is currently a 1 in the base fractal, that section will have a copy of a Hu-Tao Fractal that's 1/3rd the size of the one we're trying to make. The spot that has a 0 will be filled with 0's.

Therefore, the next Hu-Tao Fractal would look like the following:

1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1
1 0 1 0 0 0 1 0 1
1 1 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1

This pattern can of course continue repeating forever, and ever. But the fractal will always be of a size that is a power of ~3~ (~3^{k}, k \geq 1~).

Now we can also look for a Hu-Tao Fractal the other way around. First we can look for an area which has a width that is equal to a power of 3. Then we can divide that area into 9 sections, with 3 cuts to each side. All of the areas on the outside should be valid Hu-Tao Fractals, and should repeat themselves at ever smaller scales until the next fractal would be of size 0. The section at the center should be filled with 0's.

Now let's look at a valid Hu-Tao Fractal:

1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1
1 0 1 0 0 0 1 0 1
1 1 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1

This area has a side length of 9, which is a power of three. Now let's divide it up.

1 1 1 | 1 1 1 | 1 1 1
1 0 1 | 1 0 1 | 1 0 1
1 1 1 | 1 1 1 | 1 1 1
------+-------+------
1 1 1 | 0 0 0 | 1 1 1
1 0 1 | 0 0 0 | 1 0 1
1 1 1 | 0 0 0 | 1 1 1
------+-------+------
1 1 1 | 1 1 1 | 1 1 1
1 0 1 | 1 0 1 | 1 0 1
1 1 1 | 1 1 1 | 1 1 1

All the sections on the sides look like this;

1 1 1
1 0 1
1 1 1

Which is the smallest Hu-Tao Fractal which is possible. That means that the sections on the outside are good.

Now let's look at the section in the center;

0 0 0
0 0 0
0 0 0

It's all zeros! Which means that this is a valid Hu-Tao Fractal that is 9 units wide!

Knowing this, the Nerds wonder about the following problem:

"Given ~A~, an ~N~ by ~N~ square grid with all ~A_{i,j}~ being either 0 or 1, what is the size of the greatest Hu-Tao Fractal that we can identify?"

Being a nerd yourself, you decide to help them in solving the problem.

Constraints

~1 \leq N \leq 2\times10^{3}~

~A_{i,j} \in \{0,1\}~

Subtask 1 [10%]

~N=3~

Subtask 2 [30%]

~1 \leq N \leq 100~

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line will contain one integer, ~N~, the length and width of the square grid.

The next ~N~ lines will contain ~N~ space-seperated integers, consisting of only 0's and 1's.

Output Specification

Output one integer, the side length of the largest identifiable Hu-Tao Fractal.

Sample Input 1

3
1 1 1
1 0 1
1 1 1

Sample Output 1

3

Sample Input 2

9
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1
1 0 1 0 0 0 1 0 1
1 1 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1

Sample Output 2

9

Sample Input 3

4
1 1 1 1
1 0 1 1
1 1 1 1
1 1 1 1

Sample Output 3

3

Sample Input 4

3
0 0 0
0 0 1
0 0 0

Sample Output 4

0