Given a matrix a of size n * n of integers.

Let the rows of the matrix are numbered from top to bottom from 1 to n, and the columns from left to right from 1 to n. Let ai,j be the number on intersection of i - th row and j - th column.

You start the way in the cell (1, 1) and can move only down and to the right. The path must be finished in the cell (n, n). Let b1, b2, . . ., b2n−1 are integers, written in the cells that you have visited.

The cost of the path is b1 ⊕ b2 ⊕ . . . ⊕ b2n−1.

Find the path from (1, 1) to (n, n) with minimum cost.

Input

First line contains one integer n (2 ≤ n ≤ 20) - the size of the matrix.

Each of the next n lines contains n integers ai1, ai2, . . . , ain (1 ≤ aij ≤ 109).

Output

Print one integer - the lowest possible path price.

Note

The expression x ⊕ y means bitwise operation XOR, applied to the numbers x and y. This operation exists in all modern programming languages, for example, in C ++ and Java, it is designated as «ˆ», in Pascal as «xor».