Codeforces Round 846 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

greedy

math

number theory

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. GCD Partition

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

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

Input

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

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

Example

Input

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

Output

4 1 5 3 1 21

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/09/2023 18:16:25 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|