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. \)