题目描述

给定一个正整数 $N$。

我们有一个 $N$ 行 $N$ 列的网格，其中第 $i$ 行、第 $j$ 列的方格上写有数字 $A_{i,j}$。

假设这个网格的上下边界是连接的，左右边界也是连接的。换句话说，满足以下所有条件：

• $(N,i)$ 直接在 $(1,i)$ 上面，且 $(1,i)$ 直接在 $(N,i)$ 下面，其中 $1 \leq i \leq N$。
• $(i,N)$ 直接在 $(i,1)$ 左边，且 $(i,1)$ 直接在 $(i,N)$ 右边，其中 $1 \leq i \leq N$。

Takahashi 首先选择以下八个方向中的一个：上、下、左、右，以及四个对角方向。然后，他从任意一个方格开始，按所选的方向重复移动 $N-1$ 步。

在这个过程中，Takahashi 经过了 $N$ 个方格。请找出通过将这些经过方格上的数字按顺序从左到右排列所得到的最大整数的值。

输入格式

第一行输入 $N$

接下来 $N$ 行，每行输入 $N$ 个 字符 代表数字 $A_{i,j}$

输出格式

输出一个整数代表答案

4
1161
1119
7111
1811

9786

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

1111111111

提示

数据范围

• $1\ \le\ N\ \le\ 10$
• $1\ \le\ A_{i,j}\ \le\ 9$
• 输入都是整数。

样例 1 解释

如果 Takahashi 从从上数第 $2$ 行、第 $4$ 列的方格开始，按照下和右的方向移动，那么他经过的方格上的数字按顺序排列得到的整数是 $9786$。无法得到比 $9786$ 更大的值，因此答案是 $9786$。