给定一个包含n个元素的数组a[1...n],每一次“操作”包含如下四个步骤：

第一步：选择当前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行，每行一个整数。