描述

第一步：选择当前a数组的一个元素，不妨假设是a[i]

第二步：执行a[i-1] += a[i] 或者 执行a[i+1] += a[i]，注意只能执行其中之一。如果a[i-1]不存在，则不能执行a[i-1] += a[i]，同理如果a[i+1]不存在，则不能执行a[i+1] += a[i]。

第三步：把a[i]在数组中删除

第四步：数组a的元素个数减少1。

你要用最少的“操作”次数，使得a数组的每一个元素都相等，输出最少的“操作”次数

输入

多组测试数据。

第一行，一个整数R，表示有R组测试数据，1<=R<=5。

每组测试格式如下：

第一行，一个整数n。1<=n<=3000。

第二行，n个整数，第i个整数是a[i]。1<=a[i]<=100000。

输出

共R行，每行一个整数。

输入

4

5

3 1 6 6 2

4

1 2 2 1

3

2 2 2

4

6 3 2 1

输出

4

2

0

2