在基拉家的时候,仗助看到桌子上有一张纸,上面写着任务。
任务听起来如下。有一个长度为$$$n$$$的数组$$$a$$$。在此阵列上,执行以下操作:
- 选择一个整数$$$k > 1$$$;
- 将数组分割为$$$k$$$子段$$$^\dagger$$$;
- 计算每个$$$k$$$子段的总和并将这些总和写入另一个数组$$$b$$$(其中子段$$$(l, r)$$$的总和为$$${\sum_{j = l}^{r}a_j}$$$);
- 这种分割的最终分数将为 $$$\gcd(b_1, b_2, \ldots, b_k)^\ddagger$$$。
任务是找到得分最大的分区。仗助对这项任务很感兴趣,但计算机科学并不强。帮助他找到尽可能高的分数。
$$$^\dagger$$$ 将数组划分为 $$$k$$$ 子段是 $$$k$$$ 数字对 $$$(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$$$ 使得 $$$l_i \le r_i$$$ 并且对于每个 $$$1 \le j \le k - 1$$$ $$$l_{j + 1} = r_j + 1$$$,还有 $$$l_1 = 1$$$ 和 $$$r_k = n$$$。这些对代表子段。
$$$^\ddagger$$$ $$$\gcd(b_1, b_2, \ldots, b_k)$$$ 代表数组 $$$b$$$ 的最大公约数 (GCD)。
输入
第一行包含一个数字 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9 $$$) — 数组 $$$a$$$ 本身。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 最佳分区的最大分数。
示例
输入 #1
6 4 2 2 1 3 2 1 2 3 1 4 5 6 1 2 1 1 1 3 10 12 30 37 88 12 78 89 17 2 12 6 7 7 7 7 7 7
输出 #1
4 1 5 3 1 21
注意
在第一个测试用例中,您可以选择 $$$k = 2$$$ 并将数组拆分为子段 $$$(1, 2)$$$ 和 $$$(3, 4)$$$。
那么这样一个分区的分数将等于 $$$\gcd(a_1 + a_2, a_3 + a_4) = \gcd(2 + 2, 1 + 3) = \gcd(4, 4) = 4$$$。
在第四个测试用例中,您可以选择 $$$k = 3$$$ 并将数组拆分为子段 $$$(1, 2), (3, 5), (6, 6)$$$。
分割得分为 $$$\gcd(1 + 2, 1 + 1 + 1, 3) = 3$$$。