María has found a new hobby, building towers with disks. María has disks of $$$n$$$ different colors. For the $$$i$$$-th color, she has $$$a_i$$$ disks. She wants to build towers by stacking disks, but she only likes a set of towers if it meets the following conditions:
- All disks are used. - For each tower, the sequence of colors from top to bottom is the same as from bottom to top. - All towers are of equal height.
What is the minimum number of towers that María will have to build to achieve a set of towers that she likes?
The first line contains a number $$$t$$$ which is the number of cases.
The following $$$t$$$ cases each consist of the first line containing the number $$$n$$$ of colors for the case. The next line contains $$$n$$$ integers, where the $$$i$$$-th integer indicates the number of pieces of the $$$i$$$-th color.
For each case, print a single number: the minimum number of towers that María can build to create a set that she likes.
$$$ 1 \leq t \leq 100$$$
$$$ 1 \leq n \leq 10000$$$
$$$ 1 \leq a_i \leq 1000000000$$$
The sum of the $$$a_i$$$ for each case is $$$\leq 1000000000$$$
8 points: All $$$a_i$$$ are even
16 points: All $$$a_i$$$ are even except possibly one
9 points: $$$n \leq 2$$$
29 points: The sum of the $$$a_i$$$ for each case is $$$\leq 20000$$$
38 points: No additional restrictions
2 1 15 3 2 5 3
1 2
