题目背景

原题为 P8183 [USACO22FEB] Sleeping in Class B

上课请同学们好好听讲，不要睡觉。

题目描述

台风过后，Ice⭐Meow 很高兴能够重返线下课堂！不幸的是，她的老师 Gooby 讲课非常无聊，因此她经常在课堂上睡着。

Gooby 注意到 Ice⭐Meow 在课堂上没有专心听讲。他让班上的另一位学生 yoobG 记录 Ice⭐Meow 在每节课上睡着的次数。总共有 $N$ 节课（$1 \leq N \leq 10^5$），yoobG 记录到 Ice⭐Meow 在第 $i$ 节课上睡着了 $a_i$ 次（$0 \leq a_i \leq 10^6$）。所有课程中 Ice⭐Meow 睡着的总次数不超过 $10^6$。

yoobG 和 Ice⭐Meow 十分不对付，她希望让 Ice⭐Meow 在每节课上睡着的次数是一致的——从而让问题看起来完全是 Ice⭐Meow 的错，而与 Gooby 有时无聊的讲课无关。yoobG 修改记录的唯一方式是将两节相邻的课合并。例如，如果 $a = [1,2,3,4,5]$，那么如果 yoobG 合并第二和第三节课，记录将变为 $[1,5,4,5]$。

请帮助 yoobG 计算她需要对记录进行的最少修改次数，以使记录中的所有数字相等。

输入格式

每个输入包含 $T$（$1 \leq T \leq 10$）个需要独立解决的测试用例。

第一行包含 $T$，表示测试用例的数量。接下来的 $T$ 组测试用例，每组由两行描述。每组的第一行包含 $N$，第二行包含 $a_1, a_2, \ldots, a_N$。

保证每个测试用例中，$a$ 的所有值之和不超过 $10^6$。同时，所有测试用例的 $N$ 之和不超过 $10^5$。

输出格式

请输出 $T$ 行，每行表示 yoobG 为使记录中的所有数字相等所需的最少修改次数。

输入输出样例 #1

输入 #1

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

输出 #1

3
2
0

说明/提示

对于第一个测试用例，yoobG 可以通过 3 次修改将记录改为全为 $3$：

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

对于第二个测试用例，yoobG 可以通过 2 次修改将记录改为全为 $7$：

   2 2 3
-> 2 5
-> 7

对于最后一个测试用例，yoobG 不需要进行任何操作，因为记录已经由相同的数字组成。