You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Milena has received an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$ from a secret admirer. She thinks that making it non-decreasing should help her identify the secret admirer.

She can use the following operation to make this array non-decreasing:

- Select an element $$$a_i$$$ of array $$$a$$$ and an integer $$$x$$$ such that $$$1 \le x < a_i$$$. Then, replace $$$a_i$$$ by two elements $$$x$$$ and $$$a_i - x$$$ in array $$$a$$$. New elements ($$$x$$$ and $$$a_i - x$$$) are placed in the array $$$a$$$ in this order instead of $$$a_i$$$.More formally, let $$$a_1, a_2, \ldots, a_i, \ldots, a_k$$$ be an array $$$a$$$ before the operation. After the operation, it becomes equal to $$$a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k$$$. Note that the length of $$$a$$$ increases by $$$1$$$ on each operation.

Milena can perform this operation multiple times (possibly zero). She wants you to determine the minimum number of times she should perform this operation to make array $$$a$$$ non-decreasing.

An array $$$x_1, x_2, \ldots, x_k$$$ of length $$$k$$$ is called non-decreasing if $$$x_i \le x_{i+1}$$$ for all $$$1 \le i < k$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10\,000$$$). The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$) – the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

## Output Format
For each test case, output one integer — the minimum number of operations required to make the array non-decreasing.

It can be shown that it is always possible to make the array $$$a$$$ non-decreasing in the finite number of operations.

## Examples
```input
4
3
1 3 2
4
1 2 3 4
3
3 2 1
7
1 4 4 3 5 7 6
```
```output
1
0
3
9
```

## Note
In the first test case, Milena can replace the second element of array $$$a$$$ by integers $$$1$$$ and $$$2$$$, so the array would become $$$[\, 1, \, \underline{1}, \, \underline{2}, \, 2 \,]$$$. Only $$$1$$$ operation is required.

In the second test case, the array $$$a$$$ is already non-decreasing, so the answer is $$$0$$$.

In the third test case, Milena can make array $$$a$$$ non-decreasing in $$$3$$$ operations as follows.

- Select $$$i=1$$$ and $$$x=2$$$ and replace $$$a_1$$$ by $$$2$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, \underline{2}, \, \underline{1}, \, 2, \, 1 \, ]$$$.
- Select $$$i=3$$$ and $$$x=1$$$ and replace $$$a_3$$$ by $$$1$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, 2, \, 1, \, \underline{1}, \, \underline{1}, \, 1 \,]$$$.
- Select $$$i=1$$$ and $$$x=1$$$ and replace $$$a_1$$$ by $$$2$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, \underline{1}, \, \underline{1}, \, 1, \, 1, \, 1, \, 1 \,]$$$.

It can be shown that it is impossible to make it non-decreasing in $$$2$$$ or less operations, so the answer is $$$3$$$.

Now solve the problem and return the code.