CF1780B.GCD Partition

While at Kira's house, Josuke saw a piece of paper on the table with a task written on it.

The task sounded as follows. There is an array $a$ of length $n$. On this array, do the following:

• select an integer $k \gt 1$;
• split the array into $k$ subsegments $^\dagger$;
• calculate the sum in each of $k$ subsegments and write these sums to another array $b$ (where the sum of the subsegment $(l, r)$ is ${\sum_{j = l}^{r}a_j}$);
• the final score of such a split will be $\gcd(b_1, b_2, \ldots, b_k)^\ddagger$.

The task is to find such a partition that the score is maximum possible. Josuke is interested in this task but is not strong in computer science. Help him to find the maximum possible score.

$^\dagger$ A division of an array into $k$ subsegments is $k$ pairs of numbers $(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$ such that $l_i \le r_i$ and for every $1 \le j \le k - 1$ $l_{j + 1} = r_j + 1$, also $l_1 = 1$ and $r_k = n$. These pairs represent the subsegments.

$^\ddagger$ $\gcd(b_1, b_2, \ldots, b_k)$ stands for the greatest common divisor (GCD) of the array $b$.

在吉良家时，仗助看到桌上有一张纸，上面写着一道题目。

题目内容如下：给定一个长度为 $n$ 的数组 $a$。对这个数组执行以下操作：

• 选择一个整数 $k \gt 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）。

The first line contains a single number $t$ ($1 \le t \le 10^4$) — the number of test cases.

For each test case, the first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, a_3, \ldots, a_n$ ($1 \le a_i \le 10^9 $) — the array $a$ itself.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case print a single integer — the maximum score for the optimal partition.

对于每个测试用例，输出一个整数——最优划分所能得到的最大得分。

In the first test case, you can choose $k = 2$ and split the array into subsegments $(1, 2)$ and $(3, 4)$.

Then the score of such a partition will be equal to $\gcd(a_1 + a_2, a_3 + a_4) = \gcd(2 + 2, 1 + 3) = \gcd(4, 4) = 4$.

In the fourth test case, you can choose $k = 3$ and split the array into subsegments $(1, 2), (3, 5), (6, 6)$.

The split score is $\gcd(1 + 2, 1 + 1 + 1, 3) = 3$.

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