Prefix-suffix balance

One of the most popular problems presented during the initial stages of IT recruitment is that of finding a place in a sequence of integers which divides it into two groups of equal sum, i.e., at a position where the sum of the prefix is equal to the sum of the suffix. Your task is to find this position.

Input

The first line contains exactly one number t, representing the number of data sets. Each data set i is a single line, consisting of the sequence length mi and exactly mi integers which form the sequence. Numbers in data sets are separated by spaces.

Output

For each data set i print the shortest possible length of the prefix for which the sum of elements is equal to the sum of elements of the determined suffix. If desired number does not exist, then print 0. Answers for data sets should be separated by new lines.

Notes

The prefix and suffix cannot be empty.

Example

Input:
4
5 4 2 3 1 2
5 4 -2 1 1 -2
6 1 -1 1 -1 1 -1
3 0 0 0

Output:
2
0
2
1

Please log in to submit your solution.