更难游戏

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

Gildong 正在开发一款益智游戏。游戏包含 $n$ 个编号为 $1$ 到 $n$ 的平台。角色最初站在第 $1$ 个平台，目标是到达第 $n$ 个平台。

第 $i$ 个平台上标有整数 $a_i$（$0\le a_i\le n-i$）。角色站在平台 $i$ 时，可以移动到任意满足 $i+1\le j\le i+a_i$ 的平台 $j$。如果角色到达一个满足 $a_i=0$ 且 $i\ne n$ 的平台，游戏失败。

你可以把若干个平台（也可以一个都不改）的标签改成 $0$。请最小化修改的平台数，使得从平台 $1$ 到平台 $n$ 的获胜路径恰好只有一条。两条路径不同，当且仅当存在一个平台只在其中一条路径上出现。

输入格式

第一行是测试用例数 $t$（$1\le t\le 500$）。

每个测试用例包含两行：

• 第一行一个整数 $n$（$2\le n\le 3000$）；
• 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i\le n-i$）。

保证每个测试用例初始时至少有一条获胜路径，且所有测试用例的 $n$ 之和不超过 $3000$。

输出格式

对每个测试用例输出一个整数，表示使获胜路径恰好只剩一条所需的最少修改次数。

样例输入

3
4
1 1 1 0
5
4 3 2 1 0
9
4 1 4 2 1 0 2 1 0

样例输出

0
3
2

样例说明

第一个测试用例本来就只有一条路径，答案为 $0$。

第二个测试用例可以把第 $2,3,4$ 个平台改成 $0$，只保留从 $1$ 直接跳到 $5$ 的路径。

第三个测试用例可以把第 $2,8$ 个平台改成 $0$，唯一获胜路径为 $1\to3\to7\to9$。

数据范围

$1\le t\le500$，$2\le n\le3000$，$0\le a_i\le n-i$；每个测试用例初始时至少有一条获胜路径，且所有测试用例的 $n$ 之和不超过 $3000$。