You are given an array $A$ containing $N$ integers. You can apply the following operation on the array:

• Choose an index $i \;(1 \le i \le \mid A\mid)$, split $A_i$ into two positive integers $X, Y$ such that $A_i = X+Y$, remove the $i^{th}$ element from the array and append the elements $X, Y$ to the array.

Find the minimum number of operations required to make all integers of the array equal.

 Input format

• The first line contains $T$ denoting the number of test cases. The description of $T$ test cases is as follows:
• For each test case:
  • The first line contains a single integer $N$ denoting the size of array $A$.
  • The second line contains $N$ integers $A_1, A_2, \dots, A_N$ - denoting the elements of $A$.

Output format
For each test case, print the minimum number of operations required to make all integers of the array equal.

Constraints

$1 \leq T \leq 10^4 \\ 1 \leq N \leq 10^5\\ \\1\leq A_i \le 10^9 \\ Sum\; of \; N\;over\;all\;test\;cases\;does\;not\;exceed\;2\cdot 10^5.$