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