CF1898B.Milena and Admirer

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 \lt 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 \lt k$.

米莱娜从一位神秘爱慕者那里收到了一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$。她认为，将该数组变为非递减序列或许有助于她识别这位神秘爱慕者。

她可以使用以下操作使该数组变为非递减序列：

• 选择数组 $a$ 中的一个元素 $a_i$ 和一个整数 $x$，满足 $1 \le x \lt a_i$；然后将 $a_i$ 替换为两个元素 $x$ 和 $a_i - x$（按此顺序）插入到数组 $a$ 中。

  更准确地说，设操作前的数组 $a$ 为 $a_1, a_2, \ldots, a_i, \ldots, a_k$，则操作后数组变为 $a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k$。注意：每次操作会使数组 $a$ 的长度增加 $1$。

米莱娜可以执行该操作多次（也可以不执行）。请你帮她确定：使数组 $a$ 变为非递减序列所需的最少操作次数。

长度为 $k$ 的数组 $x_1, x_2, \ldots, x_k$ 称为非递减的，当且仅当对所有 $1 \le i \lt k$ 均满足 $x_i \le x_{i+1}$。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10\,000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\leq n\leq 2\cdot 10^5$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\leq a_i\leq 10^9$）—— 数组 $a$。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

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.

对于每个测试用例，输出一个整数——使数组非递减所需的最少操作次数。

可以证明：总能在有限次操作内使数组 $a$ 变为非递减。

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$.

在第一个测试用例中，米莲娜可以将数组 $a$ 的第二个元素替换为整数 $1$ 和 $2$，从而使数组变为 $[\, 1, \, \underline{1}, \, \underline{2}, \, 2 \,]$。仅需 $1$ 次操作。

在第二个测试用例中，数组 $a$ 已经是非递减的，因此答案为 $0$。

在第三个测试用例中，米莲娜可以通过 $3$ 次操作使数组 $a$ 变为非递减数组，具体如下：

• 选择 $i=1$ 和 $x=2$，将 $a_1$ 替换为 $2$ 和 $1$。数组 $a$ 变为 $[\, \underline{2}, \, \underline{1}, \, 2, \, 1 \, ]$。
• 选择 $i=3$ 和 $x=1$，将 $a_3$ 替换为 $1$ 和 $1$。数组 $a$ 变为 $[\, 2, \, 1, \, \underline{1}, \, \underline{1}, \, 1 \,]$。
• 选择 $i=1$ 和 $x=1$，将 $a_1$ 替换为 $2$ 和 $1$。数组 $a$ 变为 $[\, \underline{1}, \, \underline{1}, \, 1, \, 1, \, 1, \, 1 \,]$。

可以证明，无法在 $2$ 次或更少的操作内使其变为非递减数组，因此答案为 $3$。