暂无测试数据。

奶牛 Bessie 很高兴最近重返线下学习！不幸的是，她的导师 Farmer John 是一位非常无聊的讲师，因此她经常在课堂上打瞌睡。

Farmer John 注意到 Bessie 在课堂上没有专心听讲，因此让班上的另一名学生 Elsie 记录 Bessie 在给定课堂上睡着的次数。总共有 $N$ 节课（$1\leq N\leq 10^5$），Elsie 记录了 Bessie 在第 $i$ 节课上睡着了 $a_i$ 次（$0\leq a_i\leq 10^6$）。 Bessie 在所有课上入睡的总次数最多为 $10^6$ 次。

Elsie 因为与 Bessie 竞争非常激烈，所以想让 Farmer John 认为 Bessie 在每节课上总是以相同的次数入睡，从而让问题看起来完全是 Bessie 的错，而和 Farmer John 时不时无聊的课堂无关。 Elsie 可以修改日志的唯一方法是合并相邻两次课的日志。例如，如果 $a=[1,2,3,4,5]$，那么如果 Elsie 结合第二和第三节课，日志将变为 $[1,5,4,5]$。

请帮助 Elsie 计算她需要对日志进行的最小修改次数，以便她可以使日志中的所有数字相等。

输入格式

每个输入将包含 $T$ ($1\leq T\leq 10$) 组数据。

第一行包含 $T$，为数据组数。 接下来是 $T$ 组数据，每组数据包含两行描述。其中第一行包含 $N$，第二行包含 $a_1,a_2,...,a_N$。

保证在每组数据中，$a$ 中所有值的总和最多为 $10^6$。此外，还保证所有数据的 $N$ 之和最多为 $10^5$。

输出格式

请给出 $T$ 行输出，每行给出对应测试用例下 Elsie 需要执行的最小修改次数，以使所有日志条目都相等。

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

3
2
0