Дано матрицю a розмiру n * n з цiлих чисел.

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

Ви починаєте шлях у клiтинцi (1, 1) та можете рухатись лише вниз та вправо. Шлях потрібно закiнчити у клiтинцi (n, n). Нехай b1, b2, . . ., b2n−1 - цiлi числа, записанi в клiтинках, якi Ви вiдвiдали.

Цiна шляху дорiвнює b1 ⊕ b2 ⊕ . . . ⊕ b2n−1.

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

Вхiдні дані

Перший рядок мiстить одне цiле число n (2 ≤ n ≤ 20) - розмiр матрицi.

Кожен з наступних n рядкiв мiстить n цiлих чисел ai1, ai2, . . . , ain (1 ≤ aij ≤ 109).

Вихiдні дані

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

Примітка

Вираз x ⊕ y означає застосування побiтової операцiї XOR до чисел x та y. Дана операцiя iснує у всiх сучасних мовах програмування, наприклад, у мовах С++ i Java вона позначена як «ˆ», а в Pascal як «xor».