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

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

For each test case, output a single integer — the minimum number of passes Pekora needs to do to reduce all $S_i$ to $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$ .