Snackdown 2019 is coming! People have started to spread the word and tell other people about the contest.
There are $N$ people numbered $1$ through $N$. Initially, only person $1$ knows about Snackdown. On each day, everyone who already knows about Snackdown tells other people about it. For each valid $i$, person $i$ can tell up to $A_i$ people per day. People spread the information among the people who don't know about Snackdown in the ascending order of their indices; you may assume that no two people try to tell someone about Snackdown at the same moment. Each person is only allowed to start telling other people about Snackdown since the day after he/she gets to know about it (person $1$ can start telling other people already on day $1$). How many days does it take for all people to know about Snackdown?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the number of days.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N \le 10^5$
- the sum of $N$ for all test cases does not exceed $10^6$
- $0 \le A_i \le N$ for each valid $i$
- $1 \le A_1$

-----Example Input-----
2
7
2 1 1 5 5 5 5
5
5 1 3 2 1

-----Example Output-----
2
1

-----Explanation-----
Example case 1: On day $1$, person $1$ tells people $2$ and $3$ about Snackdown. On day $2$, the first three people know about Snackdown, so they can tell $2+1+1 = 4$ people about it in a single day. That means the last four people get to know about Snackdown on day $2$, so the total number of days is $2$.
Example case 2: On each day, person $1$ can tell up to $5$ people about Snackdown, so on the first day, he simply tells all people about it and the total number of days is $1$.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
test_case = int(input())
while test_case :
 n_people = int(input())
 array = list(map(int, input().strip().split()))
 sums =[0 for i in range(n_people)]
 
 sums[0] = array[0]
 
 for i in range(1, n_people) :
  sums[i] = sums[i-1] + array[i]
  
 # print(sums)

 k = 1 
 count = 0
 i = 0 
 while(k < n_people) :
  k = k + sums[i]
  # print(k)
  i = i + sums[i]
  count = count + 1
 print(count)
 
 
 test_case -= 1
 
  #  2  1  1  5   5   5   5
 # [2, 3, 4, 9, 14, 19, 24]
 #  0  1  2  3  4   5   6 
 
 
 
 
 
 
 
 


import sys
input=sys.stdin.readline
t=int(input())
for you in range(t):
 n=int(input())
 l=input().split()
 li=[int(i) for i in l]
 z=[]
 for i in range(n):
  z.append(li[i])
 maxpref=[0 for i in range(n)]
 maxa=0
 for i in range(n):
  maxa+=z[i]
  maxpref[i]=maxa
 curr=0
 count=0
 while(curr<n-1):
  curr+=maxpref[curr]
  count+=1
  #print(curr)
 print(count)


n=int(input())
for i in range(n):
 l=int(input())
 m=list(map(int,input().split()))
 j=0
 count=0
 days=0
 p=m[0]+1
 while(j<l):
  days+=1
  try:
   count=count+sum(m[j:j+p])
  except:
   break
  j=j+p
  p=count
 print(days)



t=int(input())
for _ in range(t):
 n=int(input())
 arr=[int(x) for x in input().split()]
 pre=[]
 pre.append(arr[0])
 for i in range(1,n):
  pre.append(arr[i]+pre[i-1])
  # print(pre[i])
 cnt=0
 day=0
 while(cnt<n-1):
  cnt+=pre[cnt]
  day+=1
  # print(cnt)
 print(day)

tcases=int(input())
lis=[]
for i in range(tcases):
 peoples=int(input())
 tells=list(map(int,input().split(" ")))
 lis.append((peoples,tells))
def days(x):
 tell=x[1]
 people=x[0]
 know=tell[0]
 add=tell[0]
 day=1
 if tell[0]+1>=people:
  return 1
 while know+1<people: 
  m=0
  for i in range(know-add+1,know+1):
   m+=tell[i]
   know+=tell[i]
  know+=add
  add+=m
  day+=1
 return day
for i in lis:
 print(days(i))

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 an=0;ix=0;cr=l[0]
 pr=[l[0]]
 for i in range(1,n):
  pr.append(pr[-1]+(l[i]))
 #print(pr)
 while ix<n-1:
  an+=1
  ix+=cr
  if ix<n-1:
   cr=pr[ix]
 print(an)


t = int(input())
while t:
 t-=1
 n = int(input())
 lst = list(map(int,input().split()))
 new = []
 su = 0
 for i in range(n):
  su = su + lst[i]
  new.append(su)
 i = 0
 ans = 0
 while(i<n-1):
  i = i+new[i]
  ans+=1
 print(ans)

t = int(input())
for i in range(t):
 N = int(input())
 An = list(map(int, input().split(" ")))
 cumsum = []
 cumsum.append(An[0])
 for j in range(N-1):
  cumsum.append(cumsum[j] + An[j+1])
 days = 0
 k = 0
 while(k < N-1):
  days += 1
  k = k + cumsum[k]
 print(days)


# cook your dish here
for _ in range(int(input())):
 a=int(input())
 arr=list(map(int,input().split()))
 i=1
 last=0
 max1=1
 sum1=0
 while(True):
  sum1+=sum(arr[last:max1])
  last=max1
  max1=sum1+last
  if(max1>=(a)):
   break
  else:
   i+=1
 print(i)




T = int(input())
for i in range(T):
 N = int(input())
 A = list(map(int,input().split()))
 
 prefix = []
 prefix.append(A[0])
 for i in range(1,N):
  prefix.append(prefix[i-1] + A[i])

 reach = 0
 days = 0
 while(reach < N - 1):
  reach = reach + prefix[reach] 
  days += 1
 print(days)


for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 s=[l[0]]+[0]*(n-1)
 for i in range(1,n):
  s[i]=s[i-1]+l[i]
 a=1
 x=s[0]+1
 while x<n:
  a=a+1
  x=x+s[x-1]
 print(a)

for case in range(int(input())):
 num = int(input())
 list1 = list(map(int, input().split()))
 list2 = [list1[0]]
 for i in range(1, num):
  list2.append(list1[i] + list2[i - 1])
 # print(list2)
 know = 1
 day = 0
 while know < num:
  day += 1
  know += list2[know - 1]
 print(day)


# cook your dish here
n=int(input())
for i in range(n):
 l=int(input())
 m=list(map(int,input().split()))
 j=0
 count=0
 days=0
 p=m[0]+1
 while(j<l):
  days+=1
  try:
   count=count+sum(m[j:j+p])
  except:
   break
  j=j+p
  p=count
 print(days)



   
  
  


'''

          Online Python Compiler.
       Code, Compile, Run and Debug python program online.
Write your code in this editor and press "Run" button to execute it.

'''

t= int(input())

for i in range(t):
 n=int(input())
 arr= list(map(int, input().split()))
 for i in range(1, n):
  arr[i]+=arr[i-1]
 days=0
 ppl=1
 
 while ppl<n:
  ppl+= arr[ppl-1]
  days+=1
  
 print(days)


t = int(input())
for i in range(0,t):
 n = int(input())
 arr = list(map(int, input().split(' ')))
 for j in range(1,n):
  arr[j]+=arr[j-1]
 j=0
 days = 0
 while True:
  days+=1
  j+=arr[j]
  if(j >= n-1):
   break
 print(days)


# cook your dish here
t=int(input())
while t > 0:
 n=int(input())
 a = list(map(int,input().split()))
 z=1
 k=0
 cnt=0
 s=1
 b=a.copy()
 g=1
 k=0 
 while g<n:
  b[g]=b[g-1]+b[g]
  g=g+1
 while z < n:
  cnt=cnt+1
  s=s+b[z-1]
  k=k+1
  if s>=n:
   break
  z=s
  if z>=n:
   break
  k=0
 print(cnt)
 t=t-1

try:
 for i in range(int(input())):
  n=int(input())
  b=input()
  b=b.split()
  b=list(map(int,b))
  day=0
  t=list(map(int,b))
  t[0]=-1
  tell=b[0]
  known=1
  q=[-1 for i in range(n)]
  for i in range(1,n):
   if t[i]!=-1:
    p=0
    c=0
    if tell>n-known:
     for j in range(i,n):
      t[j]=-1
      known+=1
      p+=1
      c+=b[j]
     day+=1
     tell+=c
    else:
     for j in range(i,i+tell):
      t[j]=-1
      known+=1
      p+=1
      c+=b[j]
     day+=1
     tell+=c
    if t==q:
     break
  print(day)

except:
 None


# cook your dish here
t = int(input())
while t > 0:
 n = int(input()) - 1
 l = list(map(int,input().split()))
 l1 = []
 c = 0
 for i in l:
  c += i
  l1.append(c)
 i = 0
 c = 0
 while n > 0:
  n = n - l1[i]
  i = i + l1[i]
  c += 1
 print(c)
 t -= 1

# cook your dish here
t=int(input())
while(t):
 t-=1 
 n=int(input())
 arr=list(map(int,input().split()))
 count=1
 i=0
 cum_sum=arr[0]
 while(cum_sum<n-1-i):
  temp=cum_sum
  # print("temp=",temp)
  for x in range(i+1,i+1+temp):
   cum_sum+=arr[x]
  i+=temp
  count+=1
  # print("left=",(n-i-1))
  # print("cum_sum=",cum_sum)
  # print("count=",count)
 print(count)

# cook your dish here
t =int(input())
while t>0:
 n=int(input())
 l=[int(x) for x in input().split()]
 s=[]
 s1=0
 for x in l:
  s1=s1+x 
  s.append(s1)
 
 d=0
 i=0
 n=n-1
 while n>0:
  n=n-s[i]
  i=i+s[i]
  d=d+1 
 print(d)
 
 
 t=t-1



# cook your dish here

t = int(input())
for i in range(t):
 n = int(input())
 l = list(map(int,input().split()))
 
 k=0
 s = 0
 l1=[0]*len(l)
 for i in l:
  s = s+i
  l1[k] = s 
  k += 1
 b = 1
 day = 0;
 while b < n:
  b += l1[b-1]
  
  day += 1
  #if b >= n:
   #   print(day)
   #  break
 print(day)