题目描述

Yuki has $n$ sticks arranged in a row, where the length of the $i$-th stick is $a_i$.

Yuki defines an operation as follows:

• Choose a stick and cut it into two parts, both of which must have integer lengths (one part can have a length of $0$).
• Merge the left part of the cut stick with the stick immediately to its left; if there is no stick to its left, the left part becomes a new, independent stick.
• Merge the right part of the cut stick with the stick immediately to its right; if there is no stick to its right, the right part becomes a new, independent stick.
• Remove all sticks with a length of $0$.

Now, Yuki wants to perform a number of operations such that all sticks have the same length. You need to help Yuki find the minimum number of operations required to make all sticks have the same length.

It can be proven that there always exists at least one sequence of operations that makes all sticks have the same length.

输入格式

This problem contains multiple test cases.

The first line contains a positive integer $t$ $(1 \le t \le 10^5)$, representing the number of test cases.

For each test case:

• The first line contains a positive integer $n$ $(1 \le n \le 10^6)$.
• The second line contains $n$ positive integers $a_1, \dots, a_n$ $(1 \le a_i \le 10^6)$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

输出格式

For each test case, output a single line containing an integer representing the minimum number of operations required to make all sticks have the same length.

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

1
2
0

提示

For the first test case:

• In the first operation, choose the second stick and cut it into two parts of lengths $4$ and $1$. The lengths of the sticks from left to right become $5, 5$, and all sticks have the same length.
• It can be proven that the minimum number of operations required is $1$.

For the second test case:

• In the first operation, choose the first stick and cut it into two parts of lengths $0$ and $1$. The lengths of the sticks from left to right become $5, 2, 5$.
• In the second operation, choose the second stick and cut it into two parts of lengths $1$ and $1$. The lengths of the sticks from left to right become $6, 6$, and all sticks have the same length.
• It can be proven that the minimum number of operations required is $2$.

For the third test case:

• Initially, all sticks have the same length, so the minimum number of operations required is $0$.