题目描述

Yuzu 有一个长为 $n$ 的序列 $\{a_i\}$。她可以做 $0$ 次或任意次操作，每次操作可以选择一对相邻的元素 $(a_i,a_{i+1})$，将它们从原序列删除，然后在相应位置插入 $a_i+a_{i+1}$。换言之，新的序列会变为 $[a_1,\ldots,a_{i-1},a_i+a_{i+1},a_{i+2},\ldots,a_n]$，且长度会减小 $1$。

Yuzu 想知道，她最少需要进行多少次操作，才可以让这个序列的所有元素都相等。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行一个正整数 $n$，代表序列长度；
• 接下来一行 $n$ 个整数，代表序列 $[a_1,a_2,\ldots,a_n]$。

输出格式

对于每组数据，输出一个整数，代表最少需要的操作次数。

4
2
6 9
3
5 2 3
5
3 6 -1 10 9
3
6 6 6

1
1
2
0

数据范围

• 对于 $30\%$ 的数据，$T \le 5$，$n \le 10$；
• 对于另外 $30\%$ 的数据，$|a_i| \le 100$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le n,\sum n \le 3 \cdot 10^4$，$|a_i| \le 3\cdot 10^4$。