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 ().

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 , an by square grid with all being either 0 or 1, what is the size of the greatest

Hu-Tao Fractalthat we can identify?"

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

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [30%]

##### Subtask 3 [60%]

No additional constraints.

#### Input Specification

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

The next lines will contain 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`

## Comments