题目描述

在 Kira 的家中，Josuke 看到桌子上有一张写着任务的纸条。

任务内容如下。有一个长度为 $n$ 的数组 $a$。对这个数组进行如下操作：

• 选择一个整数 $k > 1$；
• 将数组分成 $k$ 个子段$^\dagger$；
• 计算每个子段的和，并将这些和写入另一个数组 $b$（其中子段 $(l, r)$ 的和为 ${\sum_{j = l}^{r}a_j}$）；
• 这种划分的最终得分为 $\gcd(b_1, b_2, \ldots, b_k)^\ddagger$。

你的任务是找到一种划分方式，使得得分最大。Josuke 对这个任务很感兴趣，但他不擅长计算机科学。请你帮他找到最大可能的得分。

$^\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$。

输出格式

对于每个测试用例，输出一个整数，表示最优划分下的最大得分。

说明/提示

在第一个测试用例中，你可以选择 $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$。

由 ChatGPT 4.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

4
1
5
3
1
21