Дана матрица a размера n * n из целых чисел.

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

Вы начинаете путь в клетке (1, 1) и можете двигаться только вниз и вправо. Путь нужно закончить в клетке (n, n). Пусть b1, b2, . . ., b2n−1 - целые числа, записанные в клетках, которые Вы посетили.

Цена пути равна b1 ⊕ b2 ⊕ . . . ⊕ b2n−1.

Найдите путь от (1, 1) до (n, n) с минимальной ценой.

Входные данные

Первая строка содержит одно целое число n (2 ≤ n ≤ 20) - размер матрицы.

Каждая из следующих n строк содержит n целых чисел ai1, ai2, . . . , ain (1 ≤ aij ≤ 109).

Выходные данные

Выведите одно целое число - минимально возможную цену пути.

Примечание

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