该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

这是小静给你的考验。

Description

小静从老师那里得到了一个长度为$n$的数组，她认为数组能够不递减是非常好的数组。左思右想之后，她发现老师给的数组并不都是不递减的，她想到了一个改变数组的操作：

• 从数组$a$中选择一个元素$a_i$和一个整数$x$，使得$1 \leq x \lt a_i$.然后，用数组$a$中的两个元素$x, a_i - x$替换$a_i$。新的这两个元素将以此加入到数组中。

  更具体的说，让$a_1,a_2,...,a_i,...,a_k$变成$a_1,a_2,...,a_{i-1},x,a_i-x,a_{i+1},...,a_k$。需要注意的是，每次操作后，数组的长度都会增加$1$.

小静可以多次（可能是零次）执行上述操作。小静希望你计算出她至少要执行多少次操作才能使数组不递减。

这也算是她对你的考验吧。

Format

Input

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \leq t \leq 10000$ )。测试用例说明如下。

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

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ( $1\leq a_i\leq 10^9$ ) - 数组 $a$ 。

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

Output

输出

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

可以证明，在有限的操作次数内，总是可以使数组 $a$非递减的。

Samples

4
3
1 3 2
4
1 2 3 4
3
3 2 1
7
1 4 4 3 5 7 6

1
0
3
9

Limitation

对于20%的数据，$n$ 不会超过$100$.

对于100%的数据，满足上文的输入描述。

注

在第一个测试用例中，小静可以用整数 $1$ 和 $2$ 替换数组 $a$ 的第二个元素，这样数组就变成了 $[ 1, \underline{1}, \underline{2}, 2 ]$ 。只需要进行 $1$ 操作。

在第二个测试案例中，数组 $a$ 已经是非递减数组，所以答案是 $0$ 。

在第三个测试案例中，小静可以通过 $3$ 次运算使数组 $a$ 非递减，如下所示。

• 选择 $i=1$ 和 $x=2$ 并用 $2$ 和 $1$ 替换 $a_1$ 。数组 $a$ 就等于 $[ \underline{2}, \underline{1}, 2, 1 ]$ 。
• 选择 $i=3$ 和 $x=1$ 并用 $1$ 和 $1$ 替换 $a_3$ 。数组 $a$ 就等于 $[2, 1, \underline{1}, \underline{1}, 1 ]$ 。
• 选择 $i=1$ 和 $x=1$ ，用 $2$ 和 $1$ 替换 $a_1$ 。数组 $a$ 就等于 $[\underline{1}, \underline{1}, 1, 1, 1, 1 ]$ 。

可以证明在 $2$ 或更少的运算中不可能使数组 $a$ 非递减，因此答案是 $3$ 。