题目描述

 $ddd$最近从$xly$回来，他知道$CF$玩家$fox$喜欢收藏各种$**$，所以他给$fox$带回来了一把$AK$，并且顺序内置有$n$发子弹。他每颗子弹的威力可能不同， 这可能让有强迫症的$fox$接受不了，所以$ddd$决定请伟大的机械师$kz$来对子弹进行改造，使得剩余每一颗子弹的威力都相同，并且要求剩余的子弹尽可能多。$kz$觉得这过于$easy$，所以把这个问题交给了你。

 子弹合成规则：对于当前$a_i$, 可以与$a_{i-1}$合并，新的子弹威力变成$a_i+a_{i-1}$;当前$a_i$也 可以与$a_{i+1}$合并，新的子弹威力变成$a_i+a_{i+1}$，显然，每合成一次，子弹数量将减一。

输入格式

第一行输入一个$t$,表示$t$组测试数据。 接下来每组测试数据输入一个$n$。$({1}\leq{n}\leq{{5}\times10^3})$。 下一行输入一行，$n$个数$a_i$。$({1}\leq{a_i}\leq{10^5})$。 保证$t$组数据$\sum {n}{\leq}{{5}\times10^3}$。

输出格式

每组输出一个整数，最少合成次数

样例

2
4
1 1 2 2
3
1 1 1

1
0

提示

对于样例一:1 1 2 2，可将$a_1和a_2合并$，变成2 2 2，所以剩余子弹的最大数量为3，最少操作次数为1

来源

2022 HGNU-SWUT暑假联合集训