Pekora and Trampoline
Description
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$.
Input
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$.
Output
For each test case, output a single integer — the minimum number of passes Pekora needs to do to reduce all $S_i$ to $1$.
Samples
3
7
1 4 2 2 2 2 2
2
2 3
5
1 1 1 1 1
4
3
0
Note
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$.