Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef decided to write an infinite sequence. Initially, he wrote $0$, and then he started repeating the following process:
Look at the last element written so far (the $l$-th element if the sequence has length $l$ so far); let's denote it by $x$.
If $x$ does not occur anywhere earlier in the sequence, the next element in the sequence is $0$.
Otherwise, look at the previous occurrence of $x$ in the sequence, i.e. the $k$-th element, where $k < l$, this element is equal to $x$ and all elements between the $k+1$-th and $l-1$-th are different from $x$. The next element is $l-k$, i.e. the distance between the last two occurrences of $x$.

The resulting sequence is $(0, 0, 1, 0, 2, 0, 2, 2, 1, \ldots)$: the second element is $0$ since $0$ occurs only once in the sequence $(0)$, the third element is $1$ since the distance between the two occurrences of $0$ in the sequence $(0, 0)$ is $1$, the fourth element is $0$ since $1$ occurs only once in the sequence $(0, 0, 1)$, and so on.

Chef has given you a task to perform. Consider the $N$-th element of the sequence (denoted by $x$) and the first $N$ elements of the sequence. Find the number of occurrences of $x$ among these $N$ elements.

------  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 and only line of each test case contains a single integer $N$. 

------  Output ------
For each test case, print a single line containing one integer ― the number of occurrences of the $N$-th element.

------  Constraints  ------
$1 ≤ T ≤ 128$
$1 ≤ N ≤ 128$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ N ≤ 16$

Subtask #2 (70 points): $1 ≤ N ≤ 128$

----- Sample Input 1 ------ 
1

2
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
Example case 1: The $2$-nd element is $0$. It occurs twice among the first two elements, since the first two elements are both $0$.

Source: codechef | Difficulty: EASY
Tags: Implementation


Solutions:
t = int(input())
for t in range(t):
	n = int(input())
	l = [0]
	while len(l) < n:
		x = l[-1]
		k = -1
		for i in range(len(l) - 2, -1, -1):
			if l[i] == x:
				k = i
				break
		if k == -1:
			l.append(0)
		else:
			l.append(len(l) - 1 - k)
	print(l.count(l[-1]))


t = int(input())
for tc in range(t):
	n = int(input())
	s = [0]
	while len(s) < n:
		x = s[-1]
		k = -1
		for j in range(len(s) - 2, -1, -1):
			if s[j] == x:
				k = j
				break
		if k == -1:
			s.append(0)
		else:
			s.append(len(s) - 1 - k)
	print(s.count(s[-1]))


def search(x):
	i = 0
	tot = 0
	while i < len(les):
		if les[::-1][i] == x:
			tot = tot + 1
		if i > 0 and tot > 1:
			return i
		i = i + 1
	return 0
i = int(input())
x = 0
list1 = []
while x < i:
	pp = int(input())
	les = [0]
	k = 1
	while k <= 128:
		last_ele = les[-1]
		ad = 0
		if search(last_ele) != 0:
			ad = search(last_ele)
		les.append(ad)
		k = k + 1
	i1 = len(les[0:pp - 1])
	tot = 0
	while i1 >= 0:
		if les[i1] == les[pp - 1]:
			tot = tot + 1
		i1 = i1 - 1
	list1.append(tot)
	x = x + 1
for ele in list1:
	print(ele)


l = [0, 0, 1]
for i in range(128):
	x = l[-1]
	if x not in l[:-1]:
		l.append(0)
	else:
		count = 1
		for j in range(len(l) - 2, -1, -1):
			if l[j] == x:
				l.append(count)
				break
			else:
				count += 1
for _ in range(int(input())):
	n = int(input())
	q = l[:n]
	print(q.count(q[-1]))


l = [0]
x = 0
while True:
	if x in l[:-1]:
		k1 = len(l) - 1
		k2 = len(l) - l[::-1][1:].index(x) - 2
		l.append(k1 - k2)
		x = l[-1]
	else:
		l.append(0)
		x = 0
	if len(l) - 1 == 127:
		break
for t in range(int(input())):
	n = int(input())
	print(l[:n].count(l[n - 1]))


T = int(input())
for t in range(T):
	N = int(input())
	L = [0]
	while len(L) < N:
		x = L[-1]
		k = -1
		for i in range(len(L) - 2, -1, -1):
			if L[i] == x:
				k = i
				break
		if k == -1:
			L.append(0)
		else:
			L.append(len(L) - 1 - k)
	print(L.count(L[-1]))


t = int(input())
for ni in range(t):
	l = [0]
	n = int(input())
	for nj in range(1, n):
		if l.count(l[nj - 1]) == 1:
			l.append(0)
		else:
			pos = 0
			for i in range(0, nj - 1):
				if l[i] == l[nj - 1]:
					pos = i
			l.append(nj - 1 - pos)
	print(l.count(l[-1]))


for _ in range(int(input())):
	n = int(input())
	Flag = True
	l = [0, 0]
	if n == 1:
		print(1)
	else:
		for i in range(1, n - 1):
			x = l[i]
			for j in range(i - 1, -1, -1):
				if l[j] != x:
					Flag = False
				else:
					l.append(int(i - j))
					Flag = True
					break
			if Flag:
				pass
			else:
				l.append(0)
		count = 0
		for k in range(len(l)):
			if l[k] == l[n - 1]:
				count += 1
		print(count)


for tc in range(int(input())):
	n = int(input())
	a = []
	a.extend([0])
	for i in range(n - 1):
		x = a[-1]
		if x not in a[:-1]:
			next = 0
		else:
			next = a[-2::-1].index(x) + 1
		a.append(next)
	print(a.count(a[-1]))


for _ in range(int(input())):
	n = int(input())
	l = [0]
	k = 0
	for i in range(n - 1):
		if k in l and l.count(k) == 1:
			l.append(0)
		else:
			z = 0
			for j in range(len(l) - 1):
				if l[j] == k:
					z = j
			l.append(len(l) - 1 - z)
		k = l[len(l) - 1]
	print(l.count(l[len(l) - 1]))


A = [0, 0]
for i in range(2, 128):
	x = A[-1]
	for j in range(-2, -i - 1, -1):
		if A[j] == x:
			A.append(-1 - j)
			break
	else:
		A.append(0)
for _ in range(int(input())):
	N = int(input())
	print(A[:N].count(A[N - 1]))


for i in range(int(input())):
	n = int(input())
	lastfound = {}
	countnum = {}
	var = 0
	if n == 1:
		print(1)
	else:
		for i in range(n - 1):
			if var not in lastfound:
				countnum[var] = 1
				lastfound[var] = i
				var = 0
			else:
				temp = i - lastfound[var]
				lastfound[var] = i
				countnum[var] += 1
				var = temp
		if var in countnum:
			print(countnum[var] + 1)
		else:
			print(1)


sequence = [0]
position_dict = {0: 0}
for i in range(128):
	if sequence[i] in position_dict:
		distance = i - position_dict[sequence[i]]
		sequence.append(distance)
	else:
		sequence.append(0)
	position_dict[sequence[i]] = i
tests = int(input())
for i in range(tests):
	position = int(input())
	print(sequence[:position].count(sequence[position - 1]))


for _ in range(int(input())):
	n = int(input())
	list1 = [0, 0, 1, 0, 2, 0, 2, 2, 1, 6]
	if n <= 10:
		s = list1[:n]
		c = s.count(s[n - 1])
		print(c)
	else:
		for i in range(10, n):
			if list1.count(list1[i - 1]) >= 2:
				l = list1[:i - 1]
				l.reverse()
				p = list1[i - 1]
				ind = len(list1) - l.index(p) - 1
				list1.append(i - ind)
			else:
				list1.append(0)
		c = 0
		for i in range(n):
			if list1[i] == list1[n - 1]:
				c += 1
		print(c)


for _ in range(int(input())):
	n = int(input())
	l = [0]
	for i in range(n - 1):
		if l.count(l[i]) > 1:
			l.append(i - (i - 1 - l[i - 1::-1].index(l[i])))
		else:
			l.append(0)
	print(l.count(l[n - 1]))


for t in range(int(input())):
	n = int(input())
	l = [0]
	ind = 0
	for i in range(1, n):
		if l[i - 1] not in l[0:i - 1]:
			l.append(0)
		elif l[i - 1] in l[0:i - 1]:
			for j in range(i - 1):
				if l[j] == l[i - 1]:
					ind = j
			l.append(i - ind)
	print(l.count(l[-1]))


for _ in range(int(input())):
	n = int(input())
	li = [0, 0]
	x = 0
	for i in range(2, n):
		if li.count(li[i - 1]) >= 2:
			k = li[:i - 1]
			k.reverse()
			p = li[i - 1]
			ind = len(li) - k.index(p) - 1
			li.append(i - ind)
		else:
			li.append(0)
	c = 0
	for i in range(n):
		if li[i] == li[n - 1]:
			c += 1
	print(c)


arr = [0 for _ in range(129)]
visited = dict()
for i in range(1, 129):
	if visited.get(arr[i - 1], -1) != -1:
		arr[i] = i - 1 - visited[arr[i - 1]]
	else:
		arr[i] = 0
	visited[arr[i - 1]] = i - 1
tests = int(input())
for _ in range(tests):
	index = int(input())
	element = arr[index - 1]
	count = 0
	for i in range(index):
		if arr[i] == element:
			count += 1
	print(count)


t = int(input())
for x in range(t):
	n = int(input())
	s = {}
	a = [0] * n
	a[0] = 0
	for i in range(n):
		if i + 1 < n:
			if s.get(a[i], -1) == -1:
				a[i + 1] = 0
			else:
				a[i + 1] = i - s[a[i]]
		s[a[i]] = i
	print(a.count(a[n - 1]))


ujju = int(input())
for jyo in range(ujju):
	kk = int(input())
	saw = {}
	ty = [0] * kk
	ty[0] = 0
	for rf in range(kk):
		if rf + 1 < kk:
			if saw.get(ty[rf], -1) == -1:
				ty[rf + 1] = 0
			else:
				ty[rf + 1] = rf - saw[ty[rf]]
		saw[ty[rf]] = rf
	print(ty.count(ty[kk - 1]))


try:
	hseq = [0]
	count = 1
	for i in hseq:
		if count > 127:
			break
		if hseq.count(i) == 1:
			hseq += [0]
		else:
			val = hseq[len(hseq) - 2::-1].index(i) + 1
			hseq += [val]
		count += 1
	for j in range(int(input())):
		index = int(input())
		print(hseq[:index].count(hseq[index - 1]))
except:
	pass


li = [0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, 2, 9, 0, 4, 9, 3, 6, 14, 0, 6, 3, 5, 15, 0, 5, 3, 5, 2, 17, 0, 6, 11, 0, 3, 8, 0, 3, 3, 1, 42, 0, 5, 15, 20, 0, 4, 32, 0, 3, 11, 18, 0, 4, 7, 0, 3, 7, 3, 2, 31, 0, 6, 31, 3, 6, 3, 2, 8, 33, 0, 9, 56, 0, 3, 8, 7, 19, 0, 5, 37, 0, 3, 8, 8, 1, 46, 0, 6, 23, 0, 3, 9, 21, 0, 4, 42, 56, 25, 0, 5, 21, 8, 18, 52, 0, 6, 18, 4, 13, 0, 5, 11, 62, 0, 4, 7]
for _ in range(int(input())):
	n = int(input())
	print(li[:n].count(li[n - 1]))


t = int(input())
for _ in range(t):
	n = int(input())
	lastPos = {}
	l = [0] * n
	l[0] = 0
	for index in range(n):
		if index + 1 < n:
			if lastPos.get(l[index], -1) == -1:
				l[index + 1] = 0
			else:
				l[index + 1] = index - lastPos[l[index]]
		lastPos[l[index]] = index
	print(l.count(l[n - 1]))


for t in range(int(input())):
	N = int(input())
	sequence = [0]
	l = 0
	for i in range(1, N):
		k = 1
		while l - k >= sequence[l]:
			if sequence[l - k] == sequence[l]:
				sequence.append(k)
				break
			k += 1
		else:
			sequence.append(0)
		l += 1
	print(sequence.count(sequence[-1]))


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		a = [0, 0]
		for j in range(2, n):
			if a[j - 1] not in a[:j - 1]:
				a += [0]
			else:
				c = a[j - 2::-1]
				s = len(c) - c.index(a[j - 1]) - 1
				a += [j - 1 - s]
		print(a.count(a[n - 1]))


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		a = [0, 0]
		for i in range(2, n):
			if a[i - 1] not in a[:i - 1]:
				a += [0]
			else:
				b = a[i - 2::-1]
				c = len(b) - b.index(a[i - 1]) - 1
				a += [i - 1 - c]
		print(a.count(a[n - 1]))


for _ in range(int(input())):
	n = int(input())
	xd = {0: [0]}
	x = [0]
	for i in range(1, n):
		if len(xd[x[-1]]) == 1:
			x += [0]
			xd[0] += [i]
		else:
			a = xd[x[-1]][-1] - xd[x[-1]][-2]
			x += [a]
			if a in xd:
				xd[a] += [i]
			else:
				xd[a] = [i]
	print(len(xd[x[-1]]))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [0] * n
	for i in range(1, len(a)):
		if a[i - 1] not in a[0:i - 1]:
			a[i] = 0
		else:
			k = a[0:i - 1]
			k = k[::-1]
			p = len(k) - 1 - k.index(a[i - 1])
			a[i] = i - 1 - p
	print(a.count(a[n - 1]))


def main():
	n = int(input())
	arr = [0 for _ in range(n)]
	dic = {0: 0}
	for i in range(1, n - 1):
		num = arr[i]
		if num in dic:
			arr[i + 1] = i - dic[num]
		dic[num] = i
	x = arr[-1]
	print(arr.count(x))
t = int(input())
for _ in range(t):
	main()


def update_pos(x, i, pos):
	if x in pos:
		(pos[x][0], pos[x][1]) = (pos[x][1], i)
	else:
		pos[x] = [-1, i]
seq = [0]
last_index = {0: [-1, 0]}
for i in range(1, 129):
	x = seq[-1]
	if last_index[x][0] == -1:
		seq.append(0)
	else:
		seq.append(last_index[x][1] - last_index[x][0])
	update_pos(seq[-1], i, last_index)
freq = {}
result = []
for num in seq:
	freq[num] = freq.get(num, 0) + 1
	result.append(freq[num])
for _ in range(int(input())):
	N = int(input())
	print(result[N - 1])


def sequence(p, feq=[]):
	p.append(0)
	visited = [0] * 156
	for i in range(2, 130):
		if visited[p[i - 1]] != 0:
			p.append(i - 1 - visited[p[i - 1]])
		else:
			p.append(0)
		visited[p[i - 1]] = i - 1
	p = p[1:]
	return p
t = int(input())
for _ in range(t):
	n = int(input())
	p = []
	p.append(-1)
	res = sequence(p)
	count = 0
	a = p[n]
	for i in range(n + 1):
		if p[i] == a:
			count += 1
	print(count)


seq = [-1 for i in range(130)]
seq[0] = 0
seq[1] = 0
seq[2] = 1
for i in range(3, 130):
	pre = seq[i - 1]
	ind = -1
	for j in range(i - 2, -1, -1):
		if seq[j] == pre:
			ind = j + 1
			break
	if ind > -1:
		seq[i] = i - ind
	else:
		seq[i] = 0
for _ in range(int(input())):
	n = int(input())
	x = seq[n - 1]
	count = 0
	for i in range(n):
		if seq[i] == x:
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = [0]
	for i in range(1, n):
		pre = l[i - 1]
		if l.index(pre) != i - 1:
			for j in range(i - 2, -1, -1):
				if l[j] == pre:
					ne = i - 1 - j
					break
			l.append(ne)
		else:
			l.append(0)
	print(l.count(l[-1]))


x = [0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, 2, 9, 0, 4, 9, 3, 6, 14, 0, 6, 3, 5, 15, 0, 5, 3, 5, 2, 17, 0, 6, 11, 0, 3, 8, 0, 3, 3, 1, 42, 0, 5, 15, 20, 0, 4, 32, 0, 3, 11, 18, 0, 4, 7, 0, 3, 7, 3, 2, 31, 0, 6, 31, 3, 6, 3, 2, 8, 33, 0, 9, 56, 0, 3, 8, 7, 19, 0, 5, 37, 0, 3, 8, 8, 1, 46, 0, 6, 23, 0, 3, 9, 21, 0, 4, 42, 56, 25, 0, 5, 21, 8, 18, 52, 0, 6, 18, 4, 13, 0, 5, 11, 62, 0, 4, 7, 40]
t = int(input())
for i in range(t):
	r = int(input())
	count = 1
	for j in range(0, r - 1, 1):
		if x[r - 1] == x[j]:
			count += 1
		else:
			continue
	print(count)


MAX = 129

def seq():
	d = {}
	for i in range(MAX):
		d[i] = []
	d[0] = [0]
	arr = [None] * (MAX + 1)
	arr[0] = 0
	for i in range(MAX):
		value = d[arr[i]]
		if len(value) == 0:
			d[arr[i]].append(i)
			arr[i + 1] = 0
		else:
			arr[i + 1] = i - value[-1]
			d[arr[i]].append(i)
	return arr

def solve(arr, n):
	ele = arr[n]
	c = 0
	for i in range(n + 1):
		if arr[i] == ele:
			c += 1
	print(c)
arr = seq()
for i in range(int(input())):
	n = int(input())
	solve(arr, n - 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = [0]
	for i in range(1, n):
		prev = l[i - 1]
		if l.index(prev) != i - 1:
			for j in range(i - 2, -1, -1):
				if l[j] == prev:
					ne = i - 1 - j
					break
			l.append(ne)
		else:
			l.append(0)
	print(l.count(l[-1]))


for _ in range(int(input())):
	n = int(input())
	l = [0]
	temp = []
	for i in range(n):
		if l[i] not in temp:
			l.append(0)
		elif l[i] in temp:
			x = temp[::-1]
			ind = x.index(l[i])
			ind = abs(len(x) - 1 - ind)
			l.append(len(l) - 1 - ind)
		temp.append(l[i])
	l.pop(-1)
	x = l[-1]
	c = 0
	while x in l:
		c = c + 1
		l.remove(x)
	print(c)


T = int(input())
for i in range(T):
	n = int(input())
	arr = [None] * n
	if n == 1:
		print(1)
	else:
		arr[0] = 0
		arr[1] = 0
		for i in range(2, n):
			if arr[i - 1] in arr[0:i - 1]:
				x = arr[0:i - 1]
				arr[i] = i - 1 - (len(x) - 1 - x[::-1].index(arr[i - 1]))
			else:
				arr[i] = 0
		print(arr.count(arr[-1]))


S = (0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5)
T = int(input())
for i in range(T):
	N = int(input())
	if N <= len(S):
		k = S[:N]
		print(k.count(S[N - 1]))
	else:
		for g in range(N - len(S)):
			m = len(S) - 2
			x = S[len(S) - 1]
			while S[m] != x:
				if m == 0:
					S += (0,)
					break
				else:
					m = m - 1
			else:
				x = len(S) - m - 1
				S += (x,)
		k = S[:N]
		print(k.count(S[N - 1]))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	lst = [0, 0]
	for i in range(1, n - 1):
		temp = lst[:i]
		temp.reverse()
		try:
			reqIndex = len(temp) - temp.index(lst[i]) - 1
		except ValueError:
			reqIndex = -1
		if reqIndex == -1:
			lst.append(0)
		else:
			lst.append(i - reqIndex)
	if n == 1:
		print('1')
	else:
		print(lst.count(lst[-1]))


a = [0]
c = 1
dic = {}
while c <= 128:
	temp = a[-1]
	if temp in dic:
		ind = dic[temp]
		a.append(c - ind - 1)
		dic[temp] = c - 1
	else:
		dic[temp] = c - 1
		a.append(0)
	c += 1
t = int(input())
for _ in range(t):
	n = int(input())
	sam = a[:n]
	print(sam.count(a[n - 1]))


p = [0, 0]
for i in range(3, 130):
	l = len(p)
	c = p[-1]
	s = p[:-1]
	if c in s:
		r = s[::-1]
		e = r.index(c)
		p.append(l - (l - e - 1))
	else:
		p.append(0)
n = int(input())
for j in range(n):
	m = int(input())
	g = p[:m]
	print(g.count(g[-1]))


appr = [[] for i in range(128)]
seq = []
el = 0
for i in range(128):
	if len(appr[el]) > 1:
		el = appr[el][-1] - appr[el][-2]
	else:
		el = 0
	seq.append(el)
	appr[el].append(i)
t = int(input())
for _ in range(t):
	n = int(input())
	el = seq[n - 1]
	i = appr[el].index(n - 1)
	print(i + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = [0, 0]
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		for i in range(2, n):
			x = l[i - 1]
			if x not in l[:i - 1]:
				l.append(0)
			else:
				li = l[:i - 1]
				l.append(i - 1 - (len(li) - 1 - li[::-1].index(x)))
		print(l[:n].count(l[n - 1]))


for _ in range(int(input())):
	N = int(input())
	A = ['0']
	for i in range(1, N):
		if A.count(A[i - 1]) == 1:
			A.append('0')
		else:
			A.append(str(i - 1 - (len(A[:i - 1]) - 1 - A[:i - 1][::-1].index(A[i - 1]))))
	print(A.count(A[N - 1]))


test_case = int(input())

def hard_sequence(seq, n):
	for i in seq:
		if len(seq) <= n:
			if i not in seq[:-1]:
				seq.append(0)
			else:
				seq_copy = seq[:-1].copy()
				seq_copy.reverse()
				index_reverse = seq_copy.index(i)
				index = len(seq_copy) - 1 - index_reverse
				seq.append(len(seq) - 1 - index)
for i in range(test_case):
	n = int(input())
	seq = [0]
	hard_sequence(seq, n)
	elem = seq[n - 1]
	seq2 = seq[:n].copy()
	print(seq2.count(elem))


try:

	def search(li, x):
		for i in reversed(range(len(li))):
			if li[i] == x:
				return i

	def generate(n):
		res = [0]
		for i in range(1, n):
			if res[i - 1] in res[0:i - 1]:
				ind = search(res[0:i - 1], res[i - 1])
				res.append(abs(ind - i + 1))
			else:
				res.append(0)
		return res
	t = int(input())
	for _ in range(t):
		n = int(input())
		l = generate(n)
		c = l[n - 1]
		print(l.count(c))
except:
	pass


def lastocc(seq, i):
	j = i - 1
	while j >= 0:
		if seq[i] == seq[j]:
			return i - j
		j -= 1
	return 0
for _ in range(int(input())):
	n = int(input())
	seq = [0]
	for i in range(n - 1):
		seq.append(lastocc(seq, i))
	print(seq.count(seq[n - 1]))