B. GCD Partitiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputWhile 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.InputThe 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.OutputFor each test case print a single integer — the maximum score for the optimal partition.ExampleInput
642 2 1 321 231 4 561 2 1 1 1 31012 30 37 88 12 78 89 17 2 1267 7 7 7 7 7Output
4
1
5
3
1
21
NoteIn 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.
642 2 1 321 231 4 561 2 1 1 1 31012 30 37 88 12 78 89 17 2 1267 7 7 7 7 7
4 1 5 3 1 21 
['brute force', 'greedy', 'math', 'number theory', '*1100']