CF1453F.Even Harder

Gildong is now developing a puzzle game. The puzzle consists of $n$ platforms numbered from $1$ to $n$. The player plays the game as a character that can stand on each platform and the goal of the game is to move the character from the $1$-st platform to the $n$-th platform.

The $i$-th platform is labeled with an integer $a_i$ ($0 \le a_i \le n-i$). When the character is standing on the $i$-th platform, the player can move the character to any of the $j$-th platforms where $i+1 \le j \le i+a_i$. If the character is on the $i$-th platform where $a_i=0$ and $i \ne n$, the player loses the game.

Since Gildong thinks the current game is not hard enough, he wants to make it even harder. He wants to change some (possibly zero) labels to $0$ so that there remains exactly one way to win. He wants to modify the game as little as possible, so he's asking you to find the minimum number of platforms that should have their labels changed. Two ways are different if and only if there exists a platform the character gets to in one way but not in the other way.

吉尔东正在开发一款益智游戏。该游戏由 $n$ 个平台组成，编号从 $1$ 到 $n$。玩家操控一个角色站在各个平台上，游戏目标是将该角色从第 $1$ 个平台移动到第 $n$ 个平台。

第 $i$ 个平台标有一个整数 $a_i$（满足 $0 \le a_i \le n-i$）。当角色站在第 $i$ 个平台时，玩家可将其移动至任意第 $j$ 个平台，其中 $i+1 \le j \le i+a_i$。若角色位于第 $i$ 个平台且 $a_i = 0$（同时 $i \ne n$），则玩家输掉游戏。

由于吉尔东认为当前游戏难度不够，他希望进一步增加难度：他想将某些（可能为零个）平台的标签修改为 $0$，使得恰好存在唯一一种获胜方式。他希望尽可能少地修改平台标签，因此请你找出需要修改标签的平台的最小数量。两种获胜方式被视为不同，当且仅当存在某个平台，在其中一种方式中角色会到达该平台，而在另一种方式中不会到达。

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$).

Each test case contains two lines. The first line of each test case consists of an integer $n$ ($2 \le n \le 3000$) — the number of platforms of the game.

The second line of each test case contains $n$ integers. The $i$-th integer is $a_i$ ($0 \le a_i \le n-i$) — the integer of the $i$-th platform.

It is guaranteed that:

• For each test case, there is at least one way to win initially.
• The sum of $n$ in all test cases doesn't exceed $3000$.

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

每个测试用例包含两行。每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 3000$）—— 表示游戏中的平台数量。

每个测试用例的第二行包含 $n$ 个整数。其中第 $i$ 个整数为 $a_i$（$0 \le a_i \le n-i$）—— 表示第 $i$ 个平台上的整数。

保证满足以下条件：

• 对于每个测试用例，初始时至少存在一种获胜方式。
• 所有测试用例中 $n$ 的总和不超过 $3000$。

For each test case, print one integer — the minimum number of different labels that should be changed to $0$ so that there remains exactly one way to win.

对于每个测试用例，输出一个整数——需要改为 $0$ 的不同标签的最小数量，使得恰好存在一种获胜方式。

In the first case, the player can only move to the next platform until they get to the $4$-th platform. Since there is already only one way to win, the answer is zero.

In the second case, Gildong can change $a_2$, $a_3$, and $a_4$ to $0$ so that the game becomes $4$ $0$ $0$ $0$ $0$. Now the only way the player can win is to move directly from the $1$-st platform to the $5$-th platform.

In the third case, Gildong can change $a_2$ and $a_8$ to $0$, then the only way to win is to move in the following way: $1$ – $3$ – $7$ – $9$.

在第一种情况下，玩家只能依次移动到下一个平台，直至到达第 $4$ 个平台。由于此时已仅存在一种获胜方式，因此答案为零。

在第二种情况下，吉隆可以将 $a_2$、$a_3$ 和 $a_4$ 均改为 $0$，从而使游戏变为 $4$ $0$ $0$ $0$ $0$。此时玩家唯一能获胜的方式是从第 $1$ 个平台直接跳至第 $5$ 个平台。

在第三种情况下，吉隆可将 $a_2$ 和 $a_8$ 改为 $0$，则此时唯一能获胜的移动路径为：$1$ – $3$ – $7$ – $9$。