You are given a square grid of n rows and n columns, where each cell holds a positive integer reading (for example, sensor values recorded across a square tile floor). Two diagonals cross the grid: the main diagonal, running from the top-left cell to the bottom-right cell, and the anti-diagonal, running from the top-right cell to the bottom-left cell. A cell lies on the main diagonal when its row index equals its column index, and on the anti-diagonal when its row index plus its column index equals n-1 (using 0-based indexing); the single center cell of an odd-sized grid lies on both.

Determine the largest value that is both a prime number and located on at least one of the two diagonals. If no diagonal cell holds a prime value, report 0 instead.

Input format

The first line contains one integer n. Each of the next n lines contains n space-separated integers: the values of that row of the grid, from column 1 to column n.

Output format

Print a single integer: the largest prime value found on either diagonal, or 0 if no diagonal cell is prime.

Constraints

• 1 <= n <= 1000
• 1 <= grid value <= 4,000,000

3
2 4 6
8 5 10
12 14 3

5

2
4 6
6 4

0