# XOR Contest

# XOR path

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 `a`

be the number on intersection of _{i,j}**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 `b`

, _{1}`b`

, . . ., _{2}`b`

are integers, written in the cells that you have visited._{2n−1}

The cost of the path is `b`

⊕ _{1}`b`

⊕ . . . ⊕ _{2}`b`

._{2n−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 `a`

, _{i1}`a`

, . . . , _{i2}`a`

(_{in}**1** ≤ `a`

≤ _{ij}`10`

).^{9}

#### 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».

2 1 8 2 8

1

4 99 146 613 1416 513 5810 1515 9616 1247 5124 6284 5844 1139 6135 6427 1561

241