Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef cooks nice receipes in the cafeteria of his company. The cafe contains N boxes with food enumerated from 1 to N and are placed in a circle in clocwise order (boxes 1 and N are adjacent). Each box has unlimited amount of food with a tastyness level of A_{i}. Chef invented a definition of a magic box!
Chef picks a box i and stays in front of it. 
Now Chef eats food from box i and skips next A_{i} boxes.
Now Chef is staying at some other (probably even the same!) box and repeats. 
Box i is a magic box if at some point of such game started from box i, Chef will find himself staying in front of it again. 

When Chef came home, Chef's dog Tommy asked him about how many magic boxes were in the cafe? Help Chef to in finding that!

------ Input ------ 

The first line of the input contains an 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 denoting the number of boxes.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the tastyness levels of each box.

------ Output ------ 

For each test case, output a single line containing number of magical boxes.

------ Constraints ------ 

$1 ≤ sum of all N over all the test cases in a single test file ≤ 10^{6}$
$0 ≤ A_{i} ≤ 10^{9}$

------ Subtasks ------ 

$Subtask #1 (30 points): 1 ≤ sum of all N over all the test cases ≤ 10^{4}; 1 ≤ N ≤ 1000$

$Subtask #2 (70 points): 1 ≤ sum of all N over all the test cases ≤ 10^{6}; 1 ≤ N ≤ 10^{5}$

----- Sample Input 1 ------ 
3
4
1 1 1 1
4
3 0 0 0
4
0 0 0 2
----- Sample Output 1 ------ 
4
1
2
----- explanation 1 ------ 
Example case 1.
Here are Chef's paths if he starting from each the box:

1->3->1
2->4->2
3->1->3
4->2->4

As you see, all 4 boxes are magical.

Example case 2.
Here are Chef's paths if he starts from each box appropriately:

1->1
2->3->4->1->1
3->4->1->1
4->1->1

AS you see, only box 1 is magical.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Mathematics

Implementation


Solutions:
import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict

def dfs1(u):
	visited[u] = True
	v = (u + e[u] + 1) % n
	if visited[v] is False:
		dfs1(v)
	order.append(u)

def dfs2(u):
	visited[u] = True
	for adjacent in transpose[u]:
		if visited[adjacent] is False:
			dfs2(adjacent)
	scc.append(u)
t = int(input())
for i in range(t):
	n = int(input())
	e = [int(x) for x in input().split()]
	transpose = defaultdict(list)
	for (index, value) in enumerate(e):
		transpose[(index + value + 1) % n].append(index)
	ans = 0
	visited = [False] * n
	order = []
	for i in range(n):
		if visited[i] is False:
			dfs1(i)
	visited = [False] * n
	for i in range(n):
		node = order[n - 1 - i]
		scc = []
		if visited[node] is False:
			dfs2(node)
			if len(scc) == 1 and scc[0] != (scc[0] + e[scc[0]] + 1) % n:
				continue
			ans += len(scc)
	print(ans)


import sys
sys.setrecursionlimit(1000000)
t = int(input())

def dfs1(node, adj, vis, out):
	for child in adj[node]:
		if not vis[child]:
			vis[child] = True
			dfs1(child, adj, vis, out)
	out.append(node)

def dfs2(node, adj, vis, con):
	for child in adj[node]:
		if not vis[child]:
			vis[child] = True
			dfs2(child, adj, vis, con)
	con.append(node)
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	adjlist = [[] for i in range(n)]
	tadjlist = [[] for i in range(n)]
	counter2 = 0
	for (num, i) in enumerate(a):
		if num == (num + i + 1) % n:
			counter2 += 1
		adjlist[num].append((num + i + 1) % n)
		tadjlist[(num + i + 1) % n].append(num)
	vis = [False for i in range(n)]
	out = []
	for i in range(n):
		if not vis[i]:
			vis[i] = True
			dfs1(i, adjlist, vis, out)
	vis = [False for i in range(n)]
	counter = 0
	for i in out[::-1]:
		if not vis[i]:
			con = []
			vis[i] = True
			dfs2(i, tadjlist, vis, con)
			if len(con) == 1:
				counter += 1
	print(n - counter + counter2)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	g = defaultdict(int)
	for i in range(n):
		g[i] = (i + b[i] + 1) % n
	magic = 0
	visited = [False] * n
	for i in range(n):
		if not visited[i]:
			cycle = []
			to = i
			while not visited[to]:
				cycle.append(to)
				visited[to] = True
				to = g[to]
			if to in cycle:
				magic += len(cycle[cycle.index(to):])
	print(magic)


for _ in range(int(input())):
	n = int(input())
	z = input().split()
	a = list(map(int, z[:n]))
	mag = []
	unused = [True] * n
	for ix in range(n):
		if unused[ix]:
			cyc = []
			c = ix
			while unused[c]:
				cyc.append(c)
				unused[c] = False
				c = (c + a[c] + 1) % n
			if c in cyc:
				mx = cyc.index(c)
				mag.extend(cyc[mx:])
	print(len(mag))


import sys
sys.setrecursionlimit(int(1000000.0))
t = int(input())
from collections import defaultdict
global vis, d, tp, ol, scc

def v():
	return set()

def dfs(i):
	vis.add(i)
	for k in d[i]:
		if k not in vis:
			dfs(k)
	ol.append(i)

def dfs1(i):
	global scc
	vis.add(i)
	for k in tp[i]:
		if k not in vis:
			dfs1(k)
	scc.append(i)
for _ in range(t):
	d = defaultdict(v)
	tp = defaultdict(v)
	vis = set()
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n):
		p = i
		q = (i + arr[i] + 1) % n
		d[p].add(q)
		tp[q].add(p)
	ol = []
	for i in range(n):
		if i not in vis:
			dfs(i)
	ol.reverse()
	vis = set()
	ans = 0
	for i in ol:
		if i not in vis:
			scc = []
			dfs1(i)
			if len(scc) == 1 and i not in d[i]:
				continue
			ans += len(scc)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 6)

def dfs1(node):
	vis[node] = 1
	for kid in range(1, len(gp[node])):
		vl = gp[node][kid]
		if vis[vl] == 0:
			dfs1(vl)
	save1.append(node)

def dfs2(node):
	vis[node] = 1
	ar.append(node)
	for i in range(1, len(tgp[node])):
		vl = tgp[node][i]
		if vis[vl] == 0:
			dfs2(vl)
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split(' ')))
	gp = [[-1] for i in range(n)]
	tgp = [[-1] for i in range(n)]
	vis = [0 for i in range(n)]
	for i in range(n):
		val = (i + li[i] + 1) % n
		gp[i].append(val)
		tgp[val].append(i)
	save1 = []
	for i in range(n):
		if vis[i] == 0:
			dfs1(i)
	vis = [0 for i in range(n)]
	save1.reverse()
	c = 0
	for i in range(len(save1)):
		ar = []
		if vis[save1[i]] == 0:
			dfs2(save1[i])
			if len(ar) > 1:
				c = c + len(ar)
			if len(ar) == 1:
				if ar[0] in gp[save1[i]]:
					c = c + 1
	print(c)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(root):
	visited[root] = True
	for x in d[root]:
		if visited[x] == False:
			dfs(x)
	way.append(root)

def dfs1(root):
	visited[root] = True
	arr.append(root)
	for x in d_inv[root]:
		if visited[x] == False:
			dfs1(x)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(list)
	d_inv = defaultdict(list)
	cou = 0
	for i in range(len(a)):
		(x, y) = (i, (i + a[i] + 1) % n)
		d[x].append(y)
		d_inv[y].append(x)
	visited = [False] * n
	way = []
	for i in range(n):
		if visited[i] == False:
			dfs(i)
	visited = [False] * n
	way.reverse()
	for j in range(len(way)):
		arr = []
		if visited[way[j]] == False:
			dfs1(way[j])
			if len(arr) > 1:
				cou += len(arr)
			if len(arr) == 1:
				if way[j] in d[way[j]]:
					cou += 1
	print(cou)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	visited = [False] * n
	path = []
	count = 0
	for i in range(n):
		if not visited[i]:
			node = i
			path = []
			while not visited[node]:
				path.append(node)
				visited[node] = True
				node = (node + 1 + arr[node]) % n
			if node in path:
				cycle_node = path.index(node)
				count += len(path[cycle_node:])
	print(count)


from collections import deque
from sys import setrecursionlimit
setrecursionlimit(1000100)

class Solution(object):

	def __init__(self):
		super().__init__()

	def find_scc(self, adj, n):
		mark = [False] * n
		id = [0] * (n + 1)
		low_link = [0] * n
		in_stack = [False] * n
		mp = {}
		st = deque()
		for v in range(n):
			if mark[v]:
				continue
			self.scc(v, mark, id, low_link, adj, in_stack, st, mp)
		s = 0
		for v in range(n):
			cc = mp[low_link[v]]
			if cc == 1 and v in adj[v]:
				s += 1
			elif cc > 1:
				s += 1
		return s

	def scc(self, v, mark, id, low_link, adj, in_stack, st, mp):
		in_stack[v] = mark[v] = True
		low_link[v] = id[v] = id[-1]
		id[-1] += 1
		st.append(v)
		for n_v in adj[v]:
			if not mark[n_v]:
				self.scc(n_v, mark, id, low_link, adj, in_stack, st, mp)
			if in_stack[n_v]:
				low_link[v] = min(low_link[v], low_link[n_v])
		if id[v] == low_link[v]:
			mp[id[v]] = 0
			while st:
				mp[id[v]] += 1
				top_v = st.pop()
				in_stack[top_v] = False
				low_link[top_v] = id[v]
				if top_v == v:
					break

def main():
	sol = Solution()
	t = int(input())
	for _ in range(t):
		n = int(input())
		adj = [[] for _ in range(n)]
		sp = [int(e) for e in input().split()]
		for i in range(n):
			adj[i].append((i + sp[i] + 1) % n)
		print(sol.find_scc(adj, n))
main()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	b = [int(i) for i in input().split()]
	g = defaultdict(int)
	vis = [0] * n
	ans = 0
	for i in range(n):
		g[i] = (i + b[i] + 1) % n
	for i in range(n):
		if not vis[i]:
			cycle = []
			to = i
			while not vis[to]:
				vis[to] = 1
				cycle.append(to)
				to = g[to]
			if to in cycle:
				ans += len(cycle[cycle.index(to):])
	print(ans)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	magicBoxIndices = []
	isUnvisited = [True] * n
	for vertexIndex in range(n):
		if isUnvisited[vertexIndex]:
			curCycle = []
			curVertexIndex = vertexIndex
			while isUnvisited[curVertexIndex]:
				curCycle.append(curVertexIndex)
				isUnvisited[curVertexIndex] = False
				nextVertexIndex = (curVertexIndex + a[curVertexIndex] + 1) % n
				curVertexIndex = nextVertexIndex
			if curVertexIndex in curCycle:
				magicBoxIndicesInCurCycle = curCycle.index(curVertexIndex)
				magicBoxIndices.extend(curCycle[magicBoxIndicesInCurCycle:])
	print(len(magicBoxIndices))


for _ in range(int(input())):
	n = int(input())
	z = input().split()
	a = list(map(int, z[:n]))
	mag = 0
	vis = [0] * n
	seq = 1
	for ix in range(n):
		if vis[ix] == 0:
			thread = seq
			c = ix
			while vis[c] == 0:
				vis[c] = seq
				seq += 1
				c = (c + a[c] + 1) % n
			if vis[c] >= thread:
				mag += seq - vis[c]
	print(mag)


for i in range(int(input())):
	n = int(input())
	skip = [int(x) for x in input().split()]
	visited = [0 for i in range(n)]
	ans = 0
	for i in range(n):
		if visited[i] == 0:
			curr = i
			cycle = [curr]
			while visited[curr] == 0 or (curr in cycle and visited[curr] < 3):
				visited[curr] += 1
				cycle.append(curr)
				curr = (curr + skip[curr] + 1) % n
	for i in visited:
		if i >= 2:
			ans += 1
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	visited_boxes = set()
	cyclic_count = 0
	for i in range(n):
		path = []
		if i in visited_boxes:
			continue
		current_box = i
		while True:
			visited_boxes.add(current_box)
			path.append(current_box)
			next_box = current_box + a[current_box] + 1
			next_box = next_box % n
			if next_box > i and next_box not in visited_boxes:
				current_box = next_box
				continue
			break
		if next_box in path:
			cyclic_count += len(path[path.index(next_box):])
	print(cyclic_count)


t = int(input())
while t > 0:
	count = 0
	n = int(input())
	visited = []
	recursion = []
	parent = []
	arr = list(map(int, input().split()))
	for i in range(n):
		visited.append(0)
		parent.append(-1)
	for i in range(n):
		recursion = []
		source = i
		if visited[i] == 1:
			continue
		else:
			while visited[source] != 1:
				prev = source
				recursion.append(source)
				visited[source] = 1
				source = (source + arr[source] + 1) % n
				parent[source] = prev
			if source in recursion:
				while parent[prev] != source:
					count += 1
					prev = parent[prev]
				if source == prev:
					count += 1
				else:
					count += 2
	print(count)
	t -= 1


T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	A = [int(x) for x in input().split()]
	next = [(i + A[i] + 1) % n for i in range(n)]
	visited = set()
	accepted = set()
	for i in range(n):
		if i not in visited:
			tmp = set()
			Flag = False
			h = t = i
			while True:
				h = next[h]
				t = next[next[t]]
				tmp |= set([i, h, t])
				if h in accepted or t in accepted or h in visited or (t in visited):
					break
				if h == t:
					Flag = True
					break
			if Flag:
				accepted.add(h)
				h = next[h]
				while True:
					if h == t:
						break
					accepted.add(h)
					h = next[h]
			visited |= tmp
	print(len(accepted))


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	ans = 0
	i = 0
	checked = {}
	path = {}
	while i < n:
		if checked.get(i, -1) != -1:
			i += 1
			continue
		curr = i
		dist = {}
		distance = 0
		while checked.get(curr, -1) == -1:
			if curr == i:
				path[i] = []
			else:
				distance += 1
				dist[curr] = distance
				path[i].append(curr)
			checked[curr] = 1
			curr = (curr + arr[curr] + 1) % n
		if dist.get(curr, -1) != -1:
			chk = 1
		else:
			chk = 0
		if curr != i and chk == 1:
			ans += distance - dist[curr] + 1
		elif curr == i:
			ans += len(path[i]) + 1
		i += 1
	print(ans)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	mapping = []
	for j in range(n):
		a[j] = a[j] % n
		if n - j - 1 > a[j]:
			mapping.append(j + a[j] + 1)
		else:
			mapping.append(a[j] - (n - j - 1))
	loops = [0 for j in range(n)]
	for j in range(n):
		indices = []
		curr_index = j
		while True:
			if indices.__contains__(curr_index):
				lb = indices.index(curr_index)
				for x in indices[lb:]:
					loops[x] = 1
				break
			elif loops[curr_index] == 1:
				break
			elif loops[curr_index] == -1:
				break
			else:
				indices.append(curr_index)
				loops[curr_index] = -1
				curr_index = mapping[curr_index]
	ans.append(loops.count(1))
for i in ans:
	print(i)


def main():
	testCases = int(input())
	while testCases != 0:
		testCases -= 1
		solve()

def solve():
	N = int(input())
	taste = [int(i) for i in input().strip().split(' ')]
	visited = [False] * N
	arr = [0] * N
	indexSet = set()
	for i in range(N):
		indexSet.add(i)
	while len(indexSet) != 0:
		index = indexSet.pop()
		thisVisit = set()
		while arr[index] != 2:
			if visited[index]:
				break
			arr[index] += 1
			thisVisit.add(index)
			index = (index + taste[index] + 1) % N
		for i in thisVisit:
			visited[i] = True
	count = 0
	for i in arr:
		if i == 2:
			count += 1
	print(count)
main()


cas = int(input())
for t in range(cas):
	n = int(input())
	boxes = list(map(int, input().split()))
	circle = [0 for i in range(n)]
	for i in range(n):
		if circle[i] == 0:
			visited = []
			curr = i
			while True:
				visited.append(curr)
				curr = curr + (boxes[curr] + 1)
				curr = curr % n
				if circle[curr] == 1 or circle[curr] == -1:
					circle[i] = -1
					break
				elif curr in visited:
					idx = visited.index(curr)
					for j in visited[idx:]:
						circle[j] = 1
					for k in visited[:idx]:
						circle[k] = -1
					break
	magk = circle.count(1)
	print(magk)


nn = int(input())

def func1():
	n = int(input())
	ll = list(map(int, input().split()))
	prev = [[] for _ in range(n)]
	for i in range(n):
		nxt = (i + ll[i] + 1) % n
		prev[nxt].append(i)
	for i in range(n):
		if not prev[i]:
			j = i
			while True:
				nxt = (j + ll[j] + 1) % n
				if j in prev[nxt]:
					prev[nxt].remove(j)
				if prev[nxt]:
					break
				j = nxt
	magic = 0
	for i in range(n):
		if prev[i]:
			magic += 1
	return magic
ans = []
for _ in range(nn):
	ans.append(func1())
for a in ans:
	print(a)


import sys
F = sys.stdin

def f(a, n):
	for i in range(n):
		a[i] = (a[i] + i + 1) % n
	ret = [0] * n
	for i in range(n):
		if ret[i] > 0:
			continue
		j = i + 2
		while ret[i] == 0:
			ret[i] = j
			i = a[i]
		while ret[i] == j:
			ret[i] = 1
			i = a[i]
	return sum((1 for x in ret if x == 1))

def get_ints():
	return list(map(int, F.readline().split()))
t = int(F.readline())
for i in range(t):
	n = int(F.readline())
	print(f(get_ints(), n))


import sys
cases = int(input())
while cases > 0:
	cases -= 1
	lsize = int(input())
	data = input()
	data = list(map(int, data.split()))
	count = 0
	for x in data:
		data[count] = (x + 1 + count) % lsize
		count += 1
	count = 0
	result = 0
	visited = [False] * lsize
	inLoop = [0] * lsize
	for i in range(0, lsize):
		if not visited[i]:
			visited[i] = True
			k = data[i]
			count += 1
			tmp = False
			while count <= lsize and (not tmp):
				if not visited[k]:
					count += 1
					visited[k] = True
					k = data[k]
				elif inLoop[k] == 0:
					inLoop[i] = -1
					j = data[i]
					while j != k:
						inLoop[j] = -1
						j = data[j]
					inLoop[k] = 1
					j = data[k]
					while j != k:
						inLoop[j] = 1
						j = data[j]
					tmp = True
				elif inLoop[k] != 0:
					inLoop[i] = -1
					j = data[i]
					while j != k:
						inLoop[j] = -1
						j = data[j]
					tmp = True
	print(inLoop.count(1))


def nextver(l1, x):
	while l1[x] == 0:
		x += 1
	return x

def ans(l, l1, n, t, s):
	if t > 0:
		i = nextver(l1, s)
		s = i
		tt = []
		while l1[i] != 0:
			tt += [i]
			l1[i] = 0
			t -= 1
			i = (i + 1 + l[i]) % n
			if s - i == 1:
				s = i + 1
		if i in tt:
			return (l, l1, len(tt) - tt.index(i), t, s)
		else:
			return (l, l1, 0, t, s)
	else:
		return (l, l1, -1, t, s)
test = int(input())
while test != 0:
	test -= 1
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [1] * n
	t = n
	s = 0
	(l, l1, k, t, s) = ans(l, l1, n, t, s)
	a = 0
	while k != -1:
		a += k
		(l, l1, k, t, s) = ans(l, l1, n, t, s)
	print(a)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	a = []
	an = 0
	ta = [0] * n
	a.extend(map(int, input().split()))
	for j in range(n):
		if ta[j] == 1:
			continue
		l = j
		k = 0
		v = []
		while ta[l] == 0:
			ta[l] = 1
			v.append(l)
			k = k + a[l] + 1
			l = (l + a[l] + 1) % n
		if k >= n:
			try:
				an = an + len(v) - v.index(l)
			except:
				an = an
	ans.append(an)
for i in range(t):
	print(ans[i])


a = int(input())
while a > 0:
	n = int(input())
	move = list()
	visited = [0] * n
	arr = list(map(int, input().split(' ')))
	for i in range(0, n):
		move.insert(i, (i + arr[i] + 1) % n)
	count = 0
	for i in range(0, n):
		j = i
		se = set()
		se.clear()
		if j not in se:
			while visited[j] < 3:
				if j not in se:
					se.add(j)
					visited[j] += 1
					j = move[j]
				elif j in se:
					if visited[j] == 1:
						visited[j] += 1
						j = move[j]
					elif visited[j] == 2:
						count += 1
						visited[j] += 1
						j = move[j]
					else:
						break
	print(count)
	a = a - 1


t = int(input())
for test in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	vis = [0] * N
	what = [0] * N
	counter = 1
	ans = 0
	for i in range(N):
		if vis[i]:
			continue
		j = i
		cnt = 0
		while not vis[j]:
			what[j] = cnt
			vis[j] = counter
			cnt += 1
			j = (j + A[j] + 1) % N
		if vis[j] == counter:
			ans += cnt - what[j]
		counter += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [0] * len(a)
	cl = 0
	ans = 0
	for i in range(n):
		if b[i] == 0:
			cl += 1
			j = i
			idx = []
			while b[j] == 0:
				b[j] = cl
				idx.append(j)
				j += a[j] + 1
				j %= n
			if b[j] == cl:
				ans += 1
				while idx != [] and idx.pop() != j:
					ans += 1
	print(ans)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = []
	a = map(int, sys.stdin.readline().split())
	a = list(a)
	b = [-1] * n
	vis = []
	vis = [0] * n
	se = set()
	c = [0] * n
	for i in range(n):
		x = a[i]
		if x > n - 1:
			x = x % n
		b[i] = (x + i + 1) % n
	t = 0
	su = 0
	for i in range(n):
		s = []
		z = i
		while vis[z] != 1:
			vis[z] = 1
			s.append(z)
			z = b[z]
		if len(s) > 0 and z in s:
			y = s.index(z)
			t = len(s[y:])
			su = su + t
	print(su)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [-1] * n
	repeat = [0] * n
	for i in range(n):
		j = i
		pair = []
		again = False
		if repeat[j] == 2 or repeat[j] == 1:
			continue
		while True:
			pair.append(j)
			repeat[j] = 1
			if b[j] == -1:
				b[j] = (a[j] + j + 1) % n
			j = b[j]
			if repeat[j] == 2:
				again = True
				break
			if j in pair:
				again = False
				break
			if repeat[j] == 1:
				again = True
				break
		if again:
			continue
		index = pair.index(j)
		for x in range(index, len(pair)):
			repeat[pair[x]] = 2
	count = 0
	for i in range(n):
		if repeat[i] == 2:
			count += 1
	print(count)


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	l = list()
	for i in range(n):
		l.append(0)
	for i in range(n):
		l[(i + a[i] + 1) % n] += 1
	l1 = []
	for i in range(n):
		if l[i] == 0:
			l1.append(i)
	for i in l1:
		j = i
		while True:
			j = (j + a[j] + 1) % n
			l[j] -= 1
			if l[j] > 0:
				break
	count = 0
	for i in l:
		if i > 0:
			count += 1
	print(count)


def ismagic(A, N, Tested):
	ret = 0
	for i in range(N):
		if Tested[i] == 0:
			nextbox = i
			loop = []
			while Tested[nextbox] == 0:
				Tested[nextbox] = 1
				loop += [nextbox]
				nextbox = A[nextbox]
			if nextbox in loop:
				ret += len(loop) - loop.index(nextbox)
	return ret
T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	A0 = list(map(int, input().strip().split(' ')))
	A = {}
	Tested = {}
	for i in range(N):
		A[i] = (i + A0[i] + 1) % N
		Tested[i] = 0
	print(ismagic(A, N, Tested))


import sys
sys.setrecursionlimit(100010)

def dfs(g, s, visited, st, depth):
	st[s] = depth[0]
	visited[s] = True
	for v in g[s]:
		if v in st:
			return depth[0] - st[v] + 1
		elif not visited[v]:
			depth[0] += 1
			return dfs(g, v, visited, st, depth)
	return 0
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	g = [[] for i in range(N)]
	for (i, x) in enumerate(arr):
		to = (i + x + 1) % N
		g[i].append(to)
	visited = [False for i in range(N)]
	ans = 0
	for i in range(N):
		if not visited[i]:
			st = {}
			depth = [1]
			ans += dfs(g, i, visited, st, depth)
	print(ans)


t = int(input())
for t0 in range(t):
	n = int(input())
	li = [int(i) for i in input().strip().split()]
	gr = dict()
	for i in range(n):
		b = (i + li[i] + 1) % n
		gr[i] = b
	st = set([i for i in range(n)])
	ct = 0
	fc = [False for i in range(n)]
	while st:
		ele = st.pop()
		st.add(ele)
		a = ele
		cts = 0
		while not fc[ele]:
			cts += 1
			fc[ele] = True
			st.remove(ele)
			ele = gr[ele]
		if a != ele:
			tp = a
			ctt = 0
			while tp != ele:
				tp = gr[tp]
				ctt += 1
			cts -= ctt
			ct += cts
		elif a == ele:
			ct += cts
	print(ct)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	nxt = [0] * n
	for (i, j) in enumerate(arr):
		nxt[i] = (i + j + 1) % n
	rst = 0
	grp = [None] * n
	for i in range(n):
		if grp[i] is not None:
			continue
		stack = deque()
		j = i
		while grp[j] is None:
			stack.append(j)
			grp[j] = i
			j = nxt[j]
		if grp[j] != i:
			continue
		k = None
		while stack and k != j:
			k = stack.pop()
			rst += 1
	print(rst)


t = int(input())
for _ in range(t):
	n = int(input())
	B = [False for _ in range(n)]
	A = [int(i) for i in input().split()]
	special = [0 for _ in range(n)]
	for i in range(n):
		j = i
		if B[i]:
			continue
		V = {}
		while not B[j] and (not V.get(j, False)):
			V[j] = True
			j = (j + 1 + A[j]) % n
		store = B[j]
		ls = j
		j = i
		while not B[j]:
			B[j] = True
			j = (j + 1 + A[j]) % n
		if special[j] or store:
			continue
		j = ls
		special[j] = 1
		j = (j + 1 + A[j]) % n
		while j != ls:
			special[j] = 1
			j = (j + 1 + A[j]) % n
	print(sum(special))


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	special = set()
	notsospecial = set()
	i = 0
	while len(special) + len(notsospecial) < n:
		if i in special or i in notsospecial:
			i += 1
			continue
		path = [i]
		j = (i + a[i] + 1) % n
		while True:
			if j in special or j in notsospecial:
				notsospecial.update(set(path))
				break
			if j in path:
				istar = path.index(j)
				special.update(set(path[istar:]))
				notsospecial.update(set(path[:istar]))
				break
			path.append(j)
			j = (j + a[j] + 1) % n
		i += 1
	print(len(special))


for _ in range(int(input())):
	n = int(input())
	graph = [0] * n
	vis = [False] * n
	inloop = [0] * n
	arr = list(map(int, input().split()))
	for i in range(n):
		graph[i] = (i + 1 + arr[i]) % n
	for i in range(n):
		if not vis[i]:
			stk = [i]
			vis[i] = True
			while stk:
				j = graph[i]
				if vis[j]:
					if inloop[j] == 0:
						inloop[j] = 1
						x = stk.pop()
						inloop[x] = 1
						while x != j:
							inloop[x] = 1
							x = stk.pop()
						while stk:
							x = stk.pop()
							inloop[x] = -1
					elif inloop[j] == 1 or inloop[j] == -1:
						while stk:
							x = stk.pop()
							inloop[x] = -1
				else:
					vis[j] = True
					stk.append(j)
					i = j
	print(inloop.count(1))


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	M = [-1] * N
	for i in range(N):
		if M[i] < 0:
			k = i
			while M[k] < 0:
				M[k] = i + 1
				k += A[k] + 1
				k %= N
			while M[k] == i + 1:
				M[k] = 0
				k += A[k] + 1
				k %= N
	print(len(list(filter(lambda x: x == 0, M))))