402818: GYM100889 B Backward and Forward

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Backward and Forwardtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

An array is called a 'Mirror' if it reads the same backward and forward. For example, [23, 15, 23] is a 'Mirror' but [2, 0, 1] is not.

You are given an array A of size N. Your task is to make a given array a 'Mirror'. The only allowed operation is that you can merge two adjacent elements in the array and replace them with their sum.

Find minimum number of operations required to make given array a 'Mirror' such that it reads the same backward and forward.

Input

First line contains T(1 ≤ T ≤ 20), the number of test cases. Each test case consist of 2 lines. First line contains number N(1 ≤ N ≤ 105), size of the array. Next line contains N space separated integers Ai(0 ≤ Ai ≤ 109) denoting elements in the array A.

Output

For each test case output in one line minimum steps required to make given array a 'Mirror'.

ExampleInput
2
3
1 0 1
5
10 20 20 10 40
Output
0
3
Note

Sample test case 1:

Given array is already a 'Mirror' . So, no need to perform any operation.

Sample test case 2:

One possible sequence of operations.

Step 1 : Merge 2nd and 3rd element to get array [10, 40, 10, 40].

Step 2 : Merge 1st and 2nd element to get array [50, 10, 40].

Step 3 : Merge 2nd and 3rd element to get array [50, 50].

加入题单

上一题 下一题 算法标签: