F. Еще сложнее
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Gildong разрабатывает новую головоломку. Головоломка состоит из $$$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$$$, игрок проигрывает.

Так как 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$$$, чтобы существовал ровно один способ выиграть.

Пример
Входные данные
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
Примечание

В первом наборе входных данных, игрок может двигать только на следующую платформу, пока он не доберется до $$$4$$$-й платформы. Так как исходно есть ровно один способ выиграть, ответ равен нулю.

Во втором наборе входных данных, Gildong может поменять $$$a_2$$$, $$$a_3$$$, и $$$a_4$$$ на $$$0$$$, чтобы игра стала $$$4$$$ $$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$. Теперь единственный способ выиграть, это прыгнуть с $$$1$$$-й платформы на $$$5$$$-ю платформу.

В третьем наборе входных данных, Gildong может поменять $$$a_2$$$ и $$$a_8$$$ на $$$0$$$, тогда единственный способ выиграть это: $$$1$$$ – $$$3$$$ – $$$7$$$ – $$$9$$$.