XOR шлях

Дана матриця $a$ розміру $n\times n$, що складається з цілих чисел.

Припустимо, що рядки матриці пронумеровані зверху вниз від $1$ до $n$, а стовпці — зліва направо від $1$ до $n$. Нехай $a_{i,j}$ — число на перетині $i$-го рядка та $j$-го стовпця.

Ви починаєте шлях у клітинці $(1,1)$ і можете переміщатися тільки вниз або вправо. Шлях має закінчуватися в комірці $(n,n)$. Нехай $b_1,b_2,\dots ,b_{2n-1}$ — цілі числа, записані в комірках, які ви відвідали.

Ціна шляху визначається виразом $b_1\oplus b_2\oplus \dots \oplus b_{2n-1}$.

Знайдіть шлях від $(1,1)$ до $(n,n)$ з мінімальною ціною.

Вхідні дані

Перший рядок містить одне ціле число $n(2\le n\le 20)$ — розмір матриці.

Кожен з наступних $n$ рядків містить $n$ цілих чисел $a_{i_1},a_{i_2},\dots ,a_{i_n}(1\le a_{ij}\le 10^9)$.

Вихідні дані

Виведіть одне ціле число — мінімально можливу ціну шляху.

Приклади

Примітка

Вираз $x\oplus y$ означає застосування побітової операції XOR до чисел $x$ та $y$. Ця операція підтримується у всіх сучасних мовах програмування, наприклад, у мовах C++ та Java вона позначається як «^», а в Pascal як «xor».