注意

此处的数据是民间数据，仅供参考。

你可以在右边一栏点击「下载」以下载民间数据。

题目描述

小可可有一个 $n \times n$ 的方格，方格 $(i, j)$ 上有一个正整数 $a_{i, j}$，小可可希望从 $(1, 1)$ 走到 $(n, n)$，他只能往下或往右走，即从 $(x, y)$ 走到 $(x + 1, y)$ 或从 $(x, y)$ 走到 $(x, y + 1)$。他身上有一个正整数 $v$，$v$ 初始为 $a_{1, 1}$，小可可每走到一个格子 $(x, y)$，$v$ 会变为 $\gcd(v, a_{x, y})$。小可可想知道他走到 $(n, n)$ 时 $v$ 最大为多少。

$\gcd(i, j)$ 表示正整数 $i$ 和 $j$ 的最大公约数，即为最大的正整数 $d$ 满足 $d$ 整除 $i$ 并且 $d$ 整除 $j$。

输入格式

输入共 $n + 1$ 行。

第一行两个正整数 $n, V$。

第 $2$ 到 $n + 1$ 行每行 $n$ 个正整数，第 $i + 1$ 行第 $j$ 个数表示 $a_{i, j}$。

输出格式

输出一行一个正整数表示答案。

样例

2 20
15 16
12 9

3

样例解释

小可可的最优方案为 $(1, 1) \to (2, 1) \to (2, 2)$。

数据范围

对于 $30\%$ 的数据，$n \le 10$。

对于另外 $30\%$ 的数据，$n, V \le 100$。

对于另外 $20\%$ 的数据，保证方格内的整数在 $[1, V]$ 内均匀随机生成。

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le a_{i, j} \le V \le 10000$。