Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC).
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Pekora and Trampoline

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

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

Example

Input

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

Output

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/02/2021 19:58:50 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|