题目描述

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$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示使所有木棍的长度均相等所需的最小操作次数。

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

1
2
0

提示

对于第 $1$ 组测试数据：

• 第 $1$ 次操作选择第 $2$ 根木棍进行操作，将其分成长度为 $4,1$ 的两段，此时从左到右的木棍长度分别为 $5,5$，所有木棍的长度均相等。
• 可以证明使所有木棍的长度均相等所需的最小操作次数为 $1$ 次。

对于第 $2$ 组测试数据：

• 第 $1$ 次操作选择第 $1$ 根木棍进行操作，将其分成长度为 $0,1$ 的两段，此时从左到右的木棍长度分别为 $5,2,5$。
• 第 $2$ 次操作选择第 $2$ 根木棍进行操作，将其分成长度为 $1,1$ 的两段，此时从左到右的木棍长度分别为 $6,6$，所有木棍的长度均相等。
• 可以证明使所有木棍的长度均相等所需的最小操作次数为 $2$ 次。

对于第 $3$ 组测试数据：

• 初始时所有木棍的长度均相等，故使所有木棍的长度均相等所需的最小操作次数为 $0$ 次。