Harry is a brilliant student in the class and hence his teacher assigned him a problem. He has been given \(N\) piles of stones denoted by an array \(A\) where \(A[i]\) represents the number of stones in each of the \(i^{th}\) piles. All piles are arranged in sequence.

Harry has been asked to make this whole combination magical by performing the below operations some number of times.

• Choose any two adjacent piles and merge them after merging the new pile formed will have the sum of stones in the two piles before merging.

A combination is magical if the sequence formed by their count of stones is a palindrome. Your task is to help Harry, find the minimum number of operations needed to make the whole combination magical.

Input Format:

• The first line contains a single integer \(T\) denoting the number of test cases.
• The first line of each test case contains an integer \(N\), denoting the number of elements in the array \(A\)
• The second line of each test case contains \(N\) space-separated integers, denoting the elements of array \(A\).

Output Format:

For each test case, print the minimum number of operations needed to make the whole combination magical.

Constraints:

\(1 ≤ T ≤ 10\)

\(1 ≤ N ≤ 10^5\)

\(0 ≤ A[i] ≤ 10^9\)