Match Fixing

Interview

Time limit1sMemory limit512 MB

Summary

On an N x N gomoku board, flip exactly one white stone to black so the longest run of black stones in a row, column, or diagonal is as long as possible.

Level: Medium5 of 10
Topics: Array, Brute force, Implementation, Simulation
Solved: No attempts yet

Problem

The cats Rang and Mary are playing Nyangmok, a variant of gomoku. The rules of Nyangmok are complicated, so let us look only at how the score is computed.

Nyangmok is played on an $N \times N$ board as shown above, using black stones and white stones.

Rang plays black, and Mary plays white.

In Nyangmok, Rang's score is the length of the longest run of black stones lying consecutively in one of the directions: horizontal, vertical, or diagonal.

The owner briefly comes home, and while Mary goes out to greet them, Rang wants to swap one of Mary's stones for one of her own. That is, Rang can change one white stone into a black stone.

Write a program that finds the maximum score Rang can obtain by changing one white stone into a black stone.

Input

The first line gives the natural number $N$ . ( $2 \le N \le 1,000$ )

The next $N$ lines each contain $N$ numbers separated by spaces. They describe the state of the board before Rang swaps a stone. Each number is one of 0, 1, or 2, where 0 means an empty position, 1 means a black stone, and 2 means a white stone.

There is at least one black stone and at least one white stone.

Output

Print the maximum score Rang can obtain.

Examples1

Example 1

Input

Expected output