问题描述

给定一个正整数 $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$ 个方格。请找出按照小明访问顺序，将他访问过的方格上的数字从左到右排列后所能得到的最大整数值。

输入格式

按以下格式输入。

$N$

$A_{1,1}A_{1,2}\dots A_{1,N}$

$A_{2,1}A_{2,2}\dots A_{2,N}$

$\vdots$

$A_{N,1}A_{N,2}\dots A_{N,N}$

输出格式

一个整数表示答案。

样例

样例输入1

4
1161
1119
7111
1811

样例输出1

9786

若小明从左侧第$2$行、第$4$列的方格开始，向下并向右移动，将经过方格上书写的数字依次排列所得的整数为 $9786$。无法构造出大于 $9786$ 的数值，因此答案为 $9786$。

样例输入2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

样例输出2

1111111111

数据规模

对于 $100\%$ 的数据：

• $1 \le N \le 10$
• $1 \le A_{i,j} \le 9$

其中 约 $50\%$ 的$A_{i,j}$数据中只有 $1$ 和 $9$。