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$$$ 个平台上。如果角色位于第 $$$i$$$ 平台上,其中 $$$a_i=0$$$ 且 $$$i \ne n$$$,则玩家输掉游戏。
由于 Gildong 认为当前的游戏不够难,所以他想让它变得更难。他想将一些(可能是零)标签更改为 $$$0$$$,这样就只剩下一种获胜方式。他希望尽可能少地修改游戏,因此他要求您找到应该更改标签的最少平台数量。当且仅当存在角色以一种方式到达但不以另一种方式到达的平台时,两种方式是不同的。
输入
每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - 应更改为 $$$0$$$ 的不同标签的最小数量,以便仅存在一种获胜方式。
示例
输入 #1
3 4 1 1 1 0 5 4 3 2 1 0 9 4 1 4 2 1 0 2 1 0
输出 #1
0 3 2
注意
在第一种情况下,玩家只能移动到下一个平台,直到到达第$$$4$$$个平台。由于获胜的方法已经只有一种,所以答案是零。
在第二种情况下,Gildong 可以将 $$$a_2$$$、$$$a_3$$$ 和 $$$a_4$$$ 更改为 $$$0$$$,以便游戏变为 $$$4$$$ $$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$。现在,玩家获胜的唯一方法是直接从 $$$1$$$-st 平台移动到 $$$5$$$-th 平台。
在第三种情况下,Gildong可以将$$$a_2$$$和$$$a_8$$$更改为$$$0$$$,那么获胜的唯一方法就是按照以下方式移动:$$$1$$$ – $$$3$$$ – $$$7$$$ – $$$9$$$。