Migrated from Lutece 3206 平台跳跃

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Alice 在玩一款平台跳跃游戏，游戏内有 n 个平台从左到右依次排列，Alice 控制的人物要从最左边的一号平台跳到最右边的 n 号平台。人物在每个平台上都有不同的跳跃能力，具体来说，人物在第 i 号平台上的跳跃能力为 $a_i$ ，这意味着当人物位于第 i 号平台上时，Alice 下一步能够跳到序号在闭区间 [$i+1,i+a_i$] 内的任意一个平台。

作为一名 ACMer ，Alice 认为这样的游戏过于简单了，于是她决定将一些平台的 $a_i$ 修改为 0 ，使得游戏只有一种跳跃方案能够过关。不过因为害怕游戏出现 bug ，她决定尽可能少的修改游戏。于是她找来了你帮助她计算她至少需要修改几个平台的 $a_i$ 来使游戏的过关方案唯一。

两个跳跃方案被认为是不同的，当且仅当存在一个平台，其在一个方案中被经过了但在另一个方案中没有。

Input

第一行一个正整数 T ，代表数据组数。 每组数据中： 第一行一个正整数 n , 代表平台个数。 第二行 n 个正整数 $a_i$ ,代表人物在每个平台上的跳跃能力。

Output

每组数据一行一个正整数，代表为了使跳跃方案唯一，最少需要修改的平台数。

Samples

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

Constraints

$1<=t<=500$ $2<=n<=3000$ $0<=a_i<=n-i$ 保证所有的 n 之和不超过 3000 保证初始一定有能够过关的跳跃方案

Note

对于第二组数据： Alice可以修改 $a_2$ ,$a_3$ , $a_4$ 为 0 来满足条件。

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming