I. Non-Increasing Dilemma
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Oussama, Rami and Yessine were taking a walk at late night when they found an oil lamp. When they wiped it, a genie appeared and told them they have 3 wishes, one for each of them. Oussama took the first wish. he said: "I wish I had an infinite amount of money". The genie granted him his wish and Oussama became the world's richest person.

Rami took the second wish. He said: "I wish to become a famous mathematician". The genie granted him his wish, Rami proved the Riemann hypothesis and became the most famous mathematician in his era.

Now, it is Yessine's turn to take the last wish. He said: "I wish I could become a legendary grandmaster". However, the genie said : "that is beyond my reach".

$$$\quad$$$- "but why?", Yessine asked.

$$$\quad$$$- "to become a legendary grandmaster is the deepest desire of every human, it is the hardest wish to accomplish and I cannot grant it", answered the genie.

Yessine laid down and got depressed. The genie felt sorry for him. He said:

$$$\quad$$$- "There is a way to become one, but it is so risky".

$$$\quad$$$- "I am listening", said Yessine confidently.

$$$\quad$$$- "In order to become a legendary grandmaster, you need to prove yourself worthy. I will give a very hard problem, if you happen to solve it, your wish will be granted. If you fail however, I will have to take your soul."

Yessine accepted the challenge.

The genie said: "I shall give you an array $$$a_1,a_2,…,a_n.$$$ You have to perform this operation on the array any number of times :

$$$\quad$$$Choose an integer $$$i \in\{1,\dots,n\}$$$ and for all $$$j \ne i$$$ add $$$a[i]$$$ to $$$a[j]$$$

What is the minimum number of operations needed to make the array sorted in non-increasing order?"

Yessine found himself incapable of solving the problem. He desperately needs your help. Please save Yessine's soul.

Input

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

  1. The first line of each test case contains a single integer $$$1\le n \le 10^5:$$$ the length of the array.
  2. The second line of each test case contains $$$n$$$ integers $$$1 \le a_i \le 10^9:$$$ the elements of the array.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\times 10^5$$$.
Output

For each test case, print one integer $$$k:$$$ The minimum number of operations needed to make the array sorted in non-increasing order.

Example
Input
5
4
4 1 2 3
4
4 3 3 2
4
1 2 3 4
1
1
2
1 2
Output
2
0
3
0
1
Note

In the first test case, in the first operation, we choose $$$i = 3$$$, the array becomes $$$[6,3,2,5]$$$. In the second operation, we choose $$$i = 4$$$, the array becomes $$$[11,8,7,5].$$$