← 返回题目列表

Codeforces · 1955/G

G. 网格上的 GCD

中文机器翻译题面 查看原题

不久前,Egor 学习了求两个数最大公约数的欧几里得算法。两个数 $$$a$$$ 和 $$$b$$$ 的最大公约数是同时整除 $$$a$$$ 和 $$$b$$$ 且不留余数的最大数。有了这些知识,叶戈尔可以解决他曾经无法解决的问题。

Vasily 有一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格,整数 $$${a_i}_j$$$ 位于第 $$$i$$$ 行和第 $$$j$$$ 列的交叉点。 Egor 想要从左上角(第一行和第一列的交叉点)到右下角(最后一行和最后一列的交叉点),找到沿途所有数字的最大公约数。他只能向下和向右移动。 Egor写下了几条路径并获得了不同的GCD值。他开始对寻找最大可能的 GCD 感兴趣。

不幸的是,Egor 厌倦了计算 GCD,因此他请求你帮助找到从网格左上角到右下角路径上整数的最大 GCD。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le {10}^{4}$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 100$$$) - 网格的行数和列数。

然后,有 $$$n$$$ 行,其中第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$(1 \le a_{i,j} \le {10}^{6}$$$) — 网格中第 $$$i$$$ 行和第 $$$j$$$ 列中写入的整数。

保证所有测试用例中 $$$n \cdot m$$$ 的总和不超过 $$$2 \cdot {10}^{5}$$$。

输出

对于每个测试用例,在单独的行中输出沿从左上角单元格到右下角单元格的路径的最大可能 GCD。

示例

输入 #1

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

输出 #1

10
3
1