You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

There are \(N\) light switches in a row numbered from 1 to \(N\). Innitially all the switches are turned off as well as all the lights.

\(i\)th switch has a special power \(Ai\) which means turning on the \(i\)th switch the switch at \((i+Ai)\)th index will also be turned on automatically if there any switch exists in \((i+Ai)\)th index and the same process continues for \((i+Ai)\)th switch recursively until the end of the switches.

For example: in an arrangement of switches as {1,1,1,1,1} turning on first switch will be enough to turn on all the lights. Every switch will turn on the adjacent switch at the right side recursively.

A half-defected switch can be turned on manually or by another switch, but it can not turn on any other switch. Or in other words special power of a half-defected switch is 0. \((Ai=0)\)

You have to answer \(N\) queries. In the \(i\)th query you have to answer the minimum number of switch you need to turn on manually to turn on all the light if only the \(i\)th switch is half-defected.

To be more clear in the \(i\)th query replace the value \(Ai\)=0 and find the minimum number of switches needed to be turned on manually to turn on all the light.
Each query is independent to other.

Input

first line takes an integer T : number of testcases
each testcase takes two lines of input
first line takes an integer N : number of switches
second line takes N integers : special power of each switch

\(1 <= T <= 10^4\)
\(1 <= N <= 2*10^5\)
\(1 <= Ai <= 10^9\)
sum of \(N\) over all testcase will not exceed \(2*10^5\)

Output

for each testcase output \(N\) numbers in a single line : minimum number of switches needed to be turned on manually if the \(i-th\) switch is half-defected.

Sample

2
3
1 1 1
3
2 1 1

2 2 1 
2 2 2 

for the first testcase :
when i=1
the array becomes { 0 , 1 , 1 }
you need to turn on the switch at index 1 and 2

when i=2
the array becomes { 1 , 0 , 1 }
you need to turn on the switches at index 1 and 3

when i=3
the array becomes { 1 , 1 , 0 }
you need to turn on the switch at index 1 only

for the second testcase :
when i=1
the array becomes { 0 , 1 , 1 }
you need to turn on the switches at index 1 and 2

when i=2
the array becomes { 2 , 0 , 1 }
you need to turn on the switches at index 1 and 2

when i=3
the array becomes { 2 , 1 , 0 }
you need to turn on the switches at index 1 and 2