Yuki 有 $n$ 根排成一排的木棍，其中第 $i$ 根木棍的长度为 $a_i$。

Yuki 定义了一项操作如下：

• 选择一根木棍并将其切成两部分，两部分的长度都必须为整数（其中一部分的长度可以为 0）。
• 将切开的木棍的左半部分与紧邻其左侧的木棍合并；如果其左侧没有木棍，则左半部分成为一根新的、独立的木棍。
• 将切开的木棍的右半部分与紧邻其右侧的木棍合并；如果其右侧没有木棍，则右半部分成为一根新的、独立的木棍。
• 移除所有长度为 0 的木棍。

现在，Yuki 希望进行若干次操作，使得所有木棍的长度都相同。你需要帮助 Yuki 找到使所有木棍长度相同所需的最少操作次数。

可以证明，总是存在至少一种操作序列能够使所有木棍的长度相同。

输入格式

本题包含多个测试用例。

第一行包含一个正整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个正整数 $n$ ($1 \le n \le 10^6$)。
• 第二行包含 $n$ 个正整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^6$)。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示使所有木棍长度相同所需的最少操作次数。

样例

输入 1

3
3
1 5 4
4
1 4 2 5
5
3 3 3 3 3

输出 1

1
2
0

说明

对于第一个测试用例：

• 在第一次操作中，选择第二根木棍并将其切成长度为 4 和 1 的两部分。从左到右的木棍长度变为 5, 5，此时所有木棍的长度相同。
• 可以证明，所需的最少操作次数为 1。

对于第二个测试用例：

• 在第一次操作中，选择第一根木棍并将其切成长度为 0 和 1 的两部分。从左到右的木棍长度变为 5, 2, 5。
• 在第二次操作中，选择第二根木棍并将其切成长度为 1 和 1 的两部分。从左到右的木棍长度变为 6, 6，此时所有木棍的长度相同。
• 可以证明，所需的最少操作次数为 2。

对于第三个测试用例：

• 初始时，所有木棍的长度都相同，因此所需的最少操作次数为 0。