311247: CF1955G. GCD on a grid
Description
Not long ago, Egor learned about the Euclidean algorithm for finding the greatest common divisor of two numbers. The greatest common divisor of two numbers $a$ and $b$ is the largest number that divides both $a$ and $b$ without leaving a remainder. With this knowledge, Egor can solve a problem that he once couldn't.
Vasily has a grid with $n$ rows and $m$ columns, and the integer ${a_i}_j$ is located at the intersection of the $i$-th row and the $j$-th column. Egor wants to go from the top left corner (at the intersection of the first row and the first column) to the bottom right corner (at the intersection of the last row and the last column) and find the greatest common divisor of all the numbers along the path. He is only allowed to move down and to the right. Egor has written down several paths and obtained different GCD values. He became interested in finding the maximum possible GCD.
Unfortunately, Egor is tired of calculating GCDs, so he asks for your help in finding the maximum GCD of the integers along the path from the top left corner to the bottom right corner of the grid.
InputThe first line contains an integer $t$ ($1 \le t \le {10}^{4}$) — the number of test cases.
The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 100$) — the number of rows and columns of the grid.
Then, there are $n$ lines, where the $i$-th line contains $m$ integers $(1 \le a_{i,j} \le {10}^{6}$) — the integers written in the $i$-th row and the $j$-th column of the grid.
It is guaranteed that the sum of $n \cdot m$ does not exceed $2 \cdot {10}^{5}$ over all test cases.
OutputFor each test case, output the maximum possible GCD along the path from the top left cell to the bottom right cell in a separate line.
ExampleInput3 2 3 30 20 30 15 25 40 3 3 12 4 9 3 12 2 8 3 12 2 4 2 4 6 8 1 3 6 9Output
10 3 1
Output
Egor 最近学习了用于找出两个数字最大公约数的欧几里得算法。现在，他想要解决一个之前无法解决的问题。Vasily 有一个有 n 行 m 列的网格，网格交叉点上的整数 a_ij 位于第 i 行和第 j 列的交叉处。Egor 想要从左上角（第一行和第一列的交叉点）走到右下角（最后一行和最后一列的交叉点），并找出沿途所有数字的最大公约数。他只允许向下和向右移动。Egor 已经记录了几条路径并得到了不同的 GCD 值。他对于找出最大可能的 GCD 产生了兴趣。
输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例的数量。
- 每个测试用例的第一行包含两个整数 n 和 m（1 ≤ n, m ≤ 100）——网格的行数和列数。
- 接下来有 n 行，其中第 i 行包含 m 个整数（1 ≤ a_ij ≤ 10^6）——网格中第 i 行和第 j 列的整数。
- 保证所有测试用例中 n × m 的和不超过 2 × 10^5。
输出：
- 对于每个测试用例，输出从左上角到右下角路径上可能的最大 GCD，每个测试用例的结果占一行。
示例：
输入：
```
3
2 3
30 20 30
15 25 40
3 3
12 4 9
3 12 2
8 3 12
2 4
2 4 6 8
1 3 6 9
```
输出：
```
10
3
1
```题目大意： Egor 最近学习了用于找出两个数字最大公约数的欧几里得算法。现在，他想要解决一个之前无法解决的问题。Vasily 有一个有 n 行 m 列的网格，网格交叉点上的整数 a_ij 位于第 i 行和第 j 列的交叉处。Egor 想要从左上角（第一行和第一列的交叉点）走到右下角（最后一行和最后一列的交叉点），并找出沿途所有数字的最大公约数。他只允许向下和向右移动。Egor 已经记录了几条路径并得到了不同的 GCD 值。他对于找出最大可能的 GCD 产生了兴趣。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例的数量。 - 每个测试用例的第一行包含两个整数 n 和 m（1 ≤ n, m ≤ 100）——网格的行数和列数。 - 接下来有 n 行，其中第 i 行包含 m 个整数（1 ≤ a_ij ≤ 10^6）——网格中第 i 行和第 j 列的整数。 - 保证所有测试用例中 n × m 的和不超过 2 × 10^5。 输出： - 对于每个测试用例，输出从左上角到右下角路径上可能的最大 GCD，每个测试用例的结果占一行。 示例： 输入： ``` 3 2 3 30 20 30 15 25 40 3 3 12 4 9 3 12 2 8 3 12 2 4 2 4 6 8 1 3 6 9 ``` 输出： ``` 10 3 1 ```