CF1491C.Pekora and Trampoline

There is a trampoline park with $n$ trampolines in a line. The $i$-th of which has strength $S_i$.

Pekora can jump on trampolines in multiple passes. She starts the pass by jumping on any trampoline of her choice.

If at the moment Pekora jumps on trampoline $i$, the trampoline will launch her to position $i + S_i$, and $S_i$ will become equal to $\max(S_i-1,1)$. In other words, $S_i$ will decrease by $1$, except of the case $S_i=1$, when $S_i$ will remain equal to $1$.

If there is no trampoline in position $i + S_i$, then this pass is over. Otherwise, Pekora will continue the pass by jumping from the trampoline at position $i + S_i$ by the same rule as above.

Pekora can't stop jumping during the pass until she lands at the position larger than $n$ (in which there is no trampoline). Poor Pekora!

Pekora is a naughty rabbit and wants to ruin the trampoline park by reducing all $S_i$ to $1$. What is the minimum number of passes she needs to reduce all $S_i$ to $1$?

有一个由 $n$ 个蹦床排成一列组成的蹦床公园，其中第 $i$ 个蹦床的弹力为 $S_i$。

Pekora 可以进行多次“跳跃轮次”（passes）来跳跃这些蹦床。每次轮次开始时，她可任选一个蹦床作为起跳点。

当 Pekora 跳到第 $i$ 个蹦床时，该蹦床会将她弹射至位置 $i + S_i$，同时 $S_i$ 的值变为 $\max(S_i-1,1)$。换言之，$S_i$ 将减小 $1$；但若原本 $S_i = 1$，则 $S_i$ 保持为 $1$。

若位置 $i + S_i$ 处没有蹦床（即超出范围），则本轮次结束。否则，Pekora 将从位置 $i + S_i$ 处的蹦床上继续按上述规则跳跃。

在一轮次中，Pekora 无法中途停止跳跃，直到她落点位置大于 $n$（即落在不存在蹦床的位置）为止。可怜的 Pekora！

Pekora 是一只淘气的兔子，她想通过将所有 $S_i$ 全部减少至 $1$ 来毁掉这个蹦床公园。请问：她最少需要多少轮次才能使所有 $S_i$ 均变为 $1$？

The first line contains a single integer $t$ ($1 \le t \le 500$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 5000$) — the number of trampolines.

The second line of each test case contains $n$ integers $S_1, S_2, \dots, S_n$ ($1 \le S_i \le 10^9$), where $S_i$ is the strength of the $i$-th trampoline.

It's guaranteed that the sum of $n$ over all test cases doesn't exceed $5000$.

第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5000$）—— 蹦床的数量。

每个测试用例的第二行包含 $n$ 个整数 $S_1, S_2, \dots, S_n$（$1 \le S_i \le 10^9$），其中 $S_i$ 表示第 $i$ 个蹦床的强度。

保证所有测试用例中 $n$ 的总和不超过 $5000$。

For each test case, output a single integer — the minimum number of passes Pekora needs to do to reduce all $S_i$ to $1$.

对于每个测试用例，输出一个整数——Pekora 所需的最少通关次数，使得所有 $S_i$ 均变为 $1$。

For the first test case, here is an optimal series of passes Pekora can take. (The bolded numbers are the positions that Pekora jumps into during these passes.)

• $[1,4,\textbf{2},2,\textbf{2},2,\textbf{2}]$
• $[1,\textbf{4},1,2,1,\textbf{2},1]$
• $[1,\textbf{3},1,2,\textbf{1},\textbf{1},\textbf{1}]$
• $[1,\textbf{2},1,\textbf{2},1,\textbf{1},\textbf{1}]$

For the second test case, the optimal series of passes is show below.

• $[\textbf{2},3]$
• $[1,\textbf{3}]$
• $[1,\textbf{2}]$

For the third test case, all $S_i$ are already equal to $1$.

对于第一个测试用例，以下是Pekora可以采取的最优传球序列。（加粗的数字表示Pekora在这些传球过程中跳入的位置。）

• $[1,4,\textbf{2},2,\textbf{2},2,\textbf{2}]$
• $[1,\textbf{4},1,2,1,\textbf{2},1]$
• $[1,\textbf{3},1,2,\textbf{1},\textbf{1},\textbf{1}]$
• $[1,\textbf{2},1,\textbf{2},1,\textbf{1},\textbf{1}]$

对于第二个测试用例，最优传球序列如下所示。

• $[\textbf{2},3]$
• $[1,\textbf{3}]$
• $[1,\textbf{2}]$

对于第三个测试用例，所有 $S_i$ 已经等于 $1$。