GCD Partition
Contest: Codeforces Round 846 (Div. 2)
Difficulty rating: 1100
Tags: brute force, greedy, math, number theory

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 > 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$$$.

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
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

Example output:
4
1
5
3
1
21

Editorial:
Let's note that it doesn't make sense for us to divide into more than $$$k = 2$$$ subsegments. Let's prove it.
Let us somehow split the array $$$a$$$ into $$$m > 2$$$ subsegments : $$$b_1, b_2, \ldots, b_m$$$. Note that $$$\gcd(b_1, b_2, \ldots, b_m) \le \gcd(b_1 + b_2, b_3, \ldots, b_m)$$$, since if $$$b_1$$$ and $$$b_2$$$ were multiples of $$$\gcd(b_1, b_2 , \ldots, b_m)$$$, so $$$b_1 + b_2$$$ is also a multiple of $$$\gcd(b_1, b_2, \ldots, b_m)$$$. This means that we can use $$$b_1 + b_2$$$ instead of $$$b_1$$$ and $$$b_2$$$, and the answer will not worsen, thus it is always beneficial to use no more than $$$k = 2$$$ subsegments.
How to find the answer? Let $$$s$$$ be the array $$$a$$$. Let's say $$$pref_i = {\sum_{j = 1}^{i} a_j}$$$, then the answer is $$$\max\limits_{1 \le i < n}(\gcd(pref_i, s - pref_i)$$$.