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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
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]
	k = 1
	count = 0
	i = 0
	while k < n_people:
		k = k + sums[i]
		i = i + sums[i]
		count = count + 1
	print(count)
	test_case -= 1


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(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])
	cnt = 0
	day = 0
	while cnt < n - 1:
		cnt += pre[cnt]
		day += 1
	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))


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])
	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)


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])
	know = 1
	day = 0
	while know < num:
		day += 1
		know += list2[know - 1]
	print(day)


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)


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


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


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
		for x in range(i + 1, i + 1 + temp):
			cum_sum += arr[x]
		i += temp
		count += 1
	print(count)


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


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
	print(day)