Background

Subtask 0 uses community testdata, and Subtask 1 uses official testdata.

Problem Description

Xiaokeke has an $n \times n$ grid. Cell $(i, j)$ contains a positive integer $a_{i,j}$. Xiaokeke wants to walk from $(1, 1)$ to $(n, n)$. He can only move down or right, that is, from $(i, j)$ to $(i+1, j)$ or from $(i, j)$ to $(i, j+1)$. He has a positive integer $v$, initially $a_{1,1}$. Each time Xiaokeke arrives at a cell $(i, j)$, $v$ becomes $\gcd(v, a_{i,j})$. Xiaokeke wants to know the maximum possible value of $v$ when he reaches $(n, n)$.

$\gcd(i, j)$ denotes the greatest common divisor of positive integers $i$ and $j$, i.e., the largest positive integer $d$ such that $d$ divides $i$ and $d$ divides $j$.

Input Format

The input has a total of $n+1$ lines.

• The first line contains two positive integers $n, V$.
• Lines $2$ to $n+1$ each contain $n$ positive integers. The $j$-th number on line $i+1$ represents $a_{i,j}$.

Output Format

Output one line containing one positive integer, representing the answer.

2 20
15 16
12 9

3

Hint

Sample Explanation

Xiaokeke’s optimal route is $(1, 1) \to (2, 1) \to (2, 2)$.

Other Sample Notes

• Samples 2 to 5: see walk/walk*.in and walk/walk*.ans in the contestant directory.

Constraints

For all data, it is guaranteed that:

• $1 \le n \le 1000$.
• $1 \le a_{i,j} \le V \le 10000$.
• All input numbers are positive integers.

Translated by ChatGPT 5