CF1955G GCD on a grid

不久前，Egor 学会了用欧几里得算法求两个数的最大公约数。两个数 $a$ 和 $b$ 的最大公约数是能整除 $a$ 和 $b$ 的最大整数。掌握了这个知识后，Egor 能解决他以前不会的问题了。 Vasily 有一个 $n$ 行 $m$ 列的网格，在第 $i$ 行第 $j$ 列的交点上有一个整数 $a_{i,j}$。Egor 想从左上角（即第一行第一列的交点）走到右下角（即最后一行最后一列的交点），并计算路径上所有数字的最大公约数。他只能向下或向右移动。Egor 记录了几条路径，得到了不同的最大公约数。他现在想知道，所有可能路径中，最大公约数的最大值是多少。 不幸的是，Egor 已经厌倦了计算最大公约数，因此他请求你帮忙，找出从左上角到右下角路径上所有整数的最大可能最大公约数。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 100$），表示网格的行数和列数。 接下来有 $n$ 行，每行包含 $m$ 个整数（$1 \le a_{i,j} \le 10^6$），表示网格中第 $i$ 行第 $j$ 列的整数。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一行，表示从左上角到右下角路径上所有整数的最大可能最大公约数。

由 ChatGPT 4.1 翻译