Вам задано натуральне число \(N\). Ми маємо сітку з \(N\) рядків і \(N\) стовпців, де клітина у \(i\)-му рядку зверху та \(j\)-му стовпці зліва містить цифру \(A_{i,j}\) написано на ньому.

Припустимо, що верхній і нижній краї цієї сітки з’єднані, а також лівий і правий краї. Іншими словами, виконується все наведене нижче.

• \((N,i)\) трохи вище \((1,i)\), а \((1,i)\) трохи нижче \((N,i)\). \((1 \le i \le N)\).

• \((i,N)\) знаходиться ліворуч від \((i,1)\), а \((i,1)\) знаходиться праворуч від \((i,N)\). \((1 \le i \le N)\).

Степан спочатку вибере один із наступних восьми напрямків: вгору, вниз, ліворуч, праворуч і чотири діагональні напрямки. Потім він починає з клітинки за своїм вибором і повторює переміщення на одну клітинку у вибраному напрямку \(N-1\) раз.

У цьому процесі Степан відвідує \(N\) клітин. Знайдіть найбільше можливе значення цілого числа, отриманого розташуванням цифр, написаних на клітинах, які відвідав Степан, зліва направо в тому порядку, у якому він відвідав.

Обмеження

• \(1 \le N \le 10\)
• \(1 \le A_{i,j} \le 9\) Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(N\)

Наступні  \(N\) рядків містять  по \(N\) цілих чисел \(A_{i,j}\) без розділювачів

Формат вихідних даних

У вихідний потік виведіть відповідь

Примітка

До прикладу 1:

Якщо Степан починає роботу з клітини в 2-му рядку зверху і в 4-му стовпці зліва і йде вниз і вправо, ціле число, отримане впорядкуванням цифр, написаних на відвіданих квадратах, буде 9786. Це неможливо щоб зробити значення більшим за 9786, тож відповідь буде 9786.

Приклад вхідних даних

4
1161
1119
7111
1811

Приклад вихідних даних

9786

Приклад вхідних даних

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Приклад вихідних даних

1111111111