题目描述

小可可有一个 $n \times n$ 的方格，方格 $(i, j)$ 上有一个正整数 $a_{i,j}$。小可可希望从 $(1, 1)$ 走到 $(n, n)$，他只能往下或往右走，即从 $(i, j)$ 走到 $(i+1, j)$ 或从 $(i, j)$ 走到 $(i, j+1)$。他身上有一个正整数 $v$，初始为 $a_{1,1}$，小可可每走到一个格子 $(i, j)$，$v$ 会变为 $\gcd(v, a_{i,j})$。小可可想知道他走到 $(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}$。

输出格式

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

样例输入 1

2 20
15 16
12 9

样例输出 1

3

说明

样例解释

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

其它样例说明

• 样例 2 ~ 5：见选手目录下的 walk/walk*.in 与 walk/walk*.ans。

数据范围

对于所有数据，保证

• $1 \le n \le 1000$,
• $1 \le a_{i,j}, V \le 10000$
• 所有输入数字都是正整数。