더 어려운 퍼즐

Gildong은 퍼즐 게임을 만들고 있다. 퍼즐에는 1번부터 $n$번까지 번호가 붙은 $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$번 발판에 있고 $i\ne n$이면 플레이어는 게임에서 진다.

Gildong은 게임을 더 어렵게 만들려고 한다. 일부 값 (하나도 바꾸지 않을 수도 있다)을 $0$으로 바꿔서 이기는 방법이 정확히 하나만 남게 하려고 한다. 바꾸는 값은 최대한 적어야 한다. 두 방법이 서로 다르다는 것은 한 방법에서는 캐릭터가 도달하지만 다른 방법에서는 도달하지 않는 발판이 있다는 뜻이다. $0$으로 바꿔야 하는 값의 최소 개수를 구하라.

첫 줄에 테스트 케이스의 수 $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$을 넘지 않는다.

각 테스트 케이스마다 이기는 방법이 정확히 하나만 남도록 $0$으로 바꿔야 하는 값의 최소 개수를 한 줄에 하나씩 출력한다.

첫 번째 경우, 플레이어는 4번 발판에 도착할 때까지 다음 발판으로만 이동할 수 있다. 이미 이기는 방법이 하나뿐이므로 답은 $0$이다.

두 번째 경우, Gildong은 $a_2$, $a_3$, $a_4$를 $0$으로 바꿔서 게임을 $4\ 0\ 0\ 0\ 0$으로 만들 수 있다. 이제 이기는 방법은 1번 발판에서 5번 발판으로 바로 이동하는 것뿐이다.

세 번째 경우, Gildong은 $a_2$와 $a_8$을 $0$으로 바꿀 수 있다. 그러면 이기는 방법은 $1 \to 3 \to 7 \to 9$ 순서로 이동하는 것뿐이다.