网格路径最大公约数

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个 $n\times m$ 的正整数网格。从左上角出发，每次只能向右或向下，直到右下角。对一条路径，计算路径上所有数的最大公约数。求所有路径中该最大公约数的最大值。

输入格式

第一行是测试组数 $t$。

每组第一行包含 $n,m$，随后 $n$ 行每行包含 $m$ 个整数。

输出格式

对每组测试输出一个整数。

样例输入 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

数据范围

• $1\le t\le10^4$；
• $1\le n,m\le100$；
• $1\le a_{i,j}\le10^6$；
• 所有测试组的 $n\cdot m$ 之和不超过 $2\times10^5$。

本题采用独立测试点计分，每个测试点等分。