题目描述

给定一个正整数 $N$。

我们有一个 $N \times 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)$。

Takahashi 首先选择以下八个方向之一：上、下、左、右以及四个对角线方向之一。然后，他将从一个自己选择的方块开始，并重复沿着所选方向移动一个方块 $N-1$ 次。

在这个过程中，Takahashi 访问了 $N$ 个方块。找到按照 Takahashi 访问的顺序将方块上的数字从左到右组成的整数的最大可能值。

约束条件

• $1 \le N \le 10$
• $1 \le A_{i,j} \le 9$
• 输入中的所有值都为整数。

输入

从标准输入读入输入数据，输入格式如下：

$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

如果 Takahashi 从网格的第二行第四列的方块开始向下和向右移动，那么按照他访问的顺序将方块上的数字排列起来得到的整数为 $9786$。无法得到比 $9786$ 更大的值，因此答案是 $9786$。

示例输入2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

示例输出2

1111111111

注意，答案可能不适合 32 位整数。