Steve made the foolish decision to mine at night, and came across a monstrous creature: the chicken jockey$$$^n$$$!

A chicken jockey$$$^n$$$ consists of $$$n$$$ mobs stacked in order on top of each other, with mob $$$1$$$ at the bottom and mob $$$n$$$ at the top. Mob $$$i$$$ initially has $$$h_i$$$ health.

In one attack, Steve can deal $$$1$$$ damage to any mob. If any mob reaches $$$0$$$ or less health, it dies, and all the mobs on top of it fall down and form a new stack. The bottom mob in the new stack takes $$$1$$$ fall damage for every mob it was on top of before falling (i.e. the number of mobs below it in the previous stack, including the one that just died). This may kill it as well, in which case all mobs on top of it fall down again and the process repeats.

For example, consider a chicken jockey$$$^6$$$ with initial mob healths $$$[1, 2, 1, 3, 5, 2]$$$. If Steve damages the third mob in the stack, it dies and the mobs with health $$$[3, 5, 2]$$$ fall down in a new stack. The bottom mob takes $$$3$$$ units of fall damage so it also dies, and the mobs with health $$$[5, 2]$$$ fall down in a new stack. The bottom mob takes $$$1$$$ unit of fall damage. As a result, after Steve's first attack, there will be two stacks with healths $$$[1, 2]$$$ and $$$[4, 2]$$$.

Steve's sword's durability is low, so he wishes to know the minimum attacks required to kill all the mobs.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of mobs.

The second line of each test case contains $$$n$$$ integers $$$h_1, h_2,\ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — the initial health of each mob.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum attacks required to kill all the mobs.

Note

In the first test case, the initial stack has mobs with health $$$[3, 1, 4, 1, 2]$$$. Steve can use one attack to damage the second mob in the stack and kill it. The third mob takes $$$2$$$ units of fall damage. There are now two stacks: $$$[3]$$$ and $$$[2, 1, 2]$$$. Now Steve can kill the second mob in the second stack. The third mob in the stack takes $$$2$$$ units of fall damage, killing it. There are now two stacks: $$$[3]$$$ and $$$[2]$$$. Finally, Steve can use five attacks to kill the remaining mobs.

In the second test case, Steve can deal $$$1$$$ damage to the bottom mob in the stack. When it dies, the second mob will take $$$1$$$ unit of fall damage and die; then the third mob will take $$$1$$$ unit of fall damage and die; finally the fourth mob will take $$$1$$$ unit of fall damage and die.

Chicken Jockey

Examples