After drifting aimlessly through space for days, your team finally decides to regroup and focus on the mission. In a stroke of insight, one of your researchers makes a breakthrough: TRAPPIST-1 is located near the largest black hole in the constellation Aquarius.

Eager to follow the lead, you aim your telescope toward Aquarius and record an ~n \times n~ image representing cosmic background radiation. According to your research, the presence of a black hole is indicated by an absence of radiation, and the largest black hole will appear as the largest diamond-shaped region of zero radiation in the image. Unfortunately, space is full of radiation voids and strange patterns, so you'll have to analyze carefully to find the largest regular diamond made entirely of zeros.

Get to work. Who knows what extraterrestrial life is waiting for you!

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 500)~, the width and height of the image you have captured.

The next ~n~ lines contain ~n~ integers ~x_{i,j}~ ~(0 \leq x_{i,j} \leq 255)~, indicating the radiation reading at row ~i~ and column ~j~ in the image ~(0 \leq i,j \leq n-1)~.

Output

Output the length of the largest regular diamond with zero radiation in the image.

Clarifications

• There will always be at least ~1~ cell with a radiation reading of ~0~.
• The following are examples of shapes that are regular diamonds:

• The following are examples of shapes that are not regular diamonds:

Example

Input 1

5
0 0 2 3 9
0 0 0 0 3
3 0 5 0 0
0 0 0 3 2
3 2 1 0 3

Output 1

3

The biggest black hole is ~3 \times 3~, and is highlighted in blue below.

Input 2

7
1 1 1 0 2 2 2
1 1 0 0 0 2 2
1 0 0 0 0 0 2
0 0 0 0 0 0 0
3 0 0 0 0 0 4
3 3 0 0 0 4 4
3 3 3 0 4 4 4

Output 2

7

The biggest black hole is ~7 \times 7~.

Input 3

2
255 0
0 255

Output 3

1

A single cell with ~0~ radiation counts as a ~1 \times 1~ diamond, and is the biggest black hole in this image.