题目描述

小可可有一个 $n \times n$ 的方格，方格 $(i, j)$ 上有一个正整数 $a_{i,j}$，小可可希望从 $(1,1)$ 走到 $(n,n)$，他只能往下或往右走，即从 $(x,y)$ 走到 $(x+1,y)$ 或从 $(x,y)$ 走到 $(x,y+1)$。他身上有一个正整数 $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$。

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

输出格式

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

2 20
15 16
12 9

3

样例解释

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

输入输出样例 2 ~ 5

见选手目录下的 walk/walk*.in 与 walk/walk*.ans。

数据范围

对于所有数据，保证 $1 \leq n \leq 1000, 1 \leq a_{i,j} \leq V \leq 10000$ 且所有输入数字都是正整数。

附加样例