Equal-Sum Segments

Interview

Time limit1sMemory limit128 MB

Summary

Split an array into contiguous segments with equal sums and output the smallest possible such common sum.

Level: Easy3 of 10
Topics: Prefix sum, Greedy, Array
Solved: No attempts yet

Problem

Given a sequence of positive integers, divide it into one or more contiguous segments without changing the order. Every segment must have the same sum.

For instance, 2, 5, 1, 3, 3, 7 can be divided as (2, 5), (1, 3, 3), (7), and each segment has sum 7.

It is also allowed to keep the whole sequence as a single segment; then the common sum is the total sum of the sequence. For each given sequence, find the minimum possible common segment sum.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 50).

For each test case, the first line contains the length M (1 ≤ M ≤ 10,000) of the sequence. The next values are the M elements of the sequence. The input lists at most 10 elements per line, so the final line for a sequence may contain fewer than 10 elements. Each element is a positive integer at most 10,000.

Output

For each test case, print one line containing the minimum possible common segment sum.

Examples1

Example 1

Input

3
6
2 5 1 3 3 7
6
1 2 3 4 5 6
20
1 1 2 1 1 2 1 1 2 1
1 2 1 1 2 1 1 2 1 1

Expected output

7
21
2