C. Mr. Wow and Spells
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Wow is playing a computer game. There are $$$n$$$ monsters arranged from left to right and numbered $$$1, 2, ...., n$$$. The $$$i$$$-th monster from the left has $$$h_{i}$$$ health points. A monster will be dead if it's health points become less than or equal to $$$0$$$.

To kill the monsters, Mr. Wow can use the spells. A single spell means :

  1. Choose any arbitrary integer $$$x (1 \le x \le 10^9)$$$, which is the energy of the current spell (note that the energy of the spell might be different in different spells).
  2. Do the following for every $$$i(1 \le i \le n)$$$ from left to right :
    • If $$$x \le h_{i}$$$, then decrease $$$h_i$$$ by $$$x$$$ and make $$$x = 0$$$.
  3. If the current spell isn't used on any monster, or at least one monster died, the game will end.

What is the maximum number of spells Mr. Wow can use before the game ends?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of monsters.

The second line of each test case contains $$$n$$$ space-separated integers $$$h_{i}$$$ ($$$1 \le h_{i} \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print a single integer — the maximum number of spells Mr. Wow can use before the game ends.

Example
Input
5
3
1 2 3
3
3 2 1
3
2 1 4
4
2 3 8 4
4
7 17 8 11
Output
1
3
3
7
23
Note

In the $$$1$$$-st test case, for any value of $$$x$$$, the game will end after using $$$1$$$ spell.

In the $$$3$$$-rd test case, we can do the following $$$3$$$ operations:

  1. Choose $$$x=1$$$. After that, $$$h=[1,1,4]$$$;
  2. Choose $$$x=3$$$; After that, $$$h=[1,1,1]$$$;
  3. Choose $$$x=1$$$; After that, $$$h=[0,1,1]$$$. The game ends because the first monster is dead.

It can be proven $$$3$$$ reaches the maximum.