Partition Point in an Array

Given an array of integers, the task is to find the partition point. The partition point is defined as an index \( k \) (0-indexed) such that the sum of the elements on the left side of \( k \) is equal to the sum of the elements on the right side of \( k \). If no such index exists, output \(-1\).

You are given multiple test cases. For each test case, you are provided with the size of the array followed by the integer elements. Your program should compute and print the partition index for each test case on separate lines.

Note: The index \( k \) partitions the array into two parts: elements at indices \(0, 1, \ldots, k-1\) and elements at indices \(k+1, k+2, \ldots, n-1\). The element at index \( k \) is not included in either sum.

For instance, for the array [1, 2, 3, 4, 6], the partition point is 3 since \(1+2+3 = 6\) and the element 4 at index 3 is the partition point, omitting itself from both sums.

inputFormat

The first line of input contains an integer \( T \) indicating the number of test cases. Then for each test case:

• The first line contains an integer \( n \), the size of the array.
• The second line contains \( n \) space-separated integers representing the array.

outputFormat

For each test case, print a single line containing the partition index. If no partition index exists, print \(-1\).

## sample

2
5
1 2 3 4 6
4
1 1 1 2

3
2

</p>