XOR path

Given a matrix $a$ of size $n\times n$ consisting of integers.

Assume that the rows of the matrix are numbered from top to bottom from $1$ to $n$, and the columns are numbered from left to right from $1$ to $n$. Let $a_{i,j}$ denote the number at the intersection of the $i$-th row and the $j$-th column.

You start your path in the cell $(1,1)$ and can move only down or right. The path must end in the cell $(n,n)$. Let $b_1,b_2,\dots ,b_{2n-1}$ be the integers written in the cells you visited.

The cost of the path is defined by the expression $b_1\oplus b_2\oplus \dots \oplus b_{2n-1}$.

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

Input

The first line contains a single integer $n(2\le n\le 20)$ — the size of the matrix.

Each of the following $n$ lines contains $n$ integers $a_{i_1},a_{i_2},\dots ,a_{i_n}(1\le a_{ij}\le 10^9)$.

Output

Output a single integer — the minimum possible cost of the path.

Examples

Note

The expression $x\oplus y$ denotes the bitwise XOR operation applied to the numbers $x$ and $y$. This operation is supported in all modern programming languages; for example, in C++ and Java, it is denoted as "^", and in Pascal as "xor".