The Fibonacci sequence $F_0, F_1, \ldots$ is a special infinite sequence of non-negative integers, where $F_0 = 0$, $F_1 = 1$ and for each integer $n \ge 2$, $F_n = F_{n-1} + F_{n-2}$.
Consider the sequence $D$ of the last decimal digits of the first $N$ Fibonacci numbers, i.e. $D = (F_0 \% 10, F_1 \% 10, \ldots, F_{N-1} \% 10)$. Now, you should perform the following process:
- Let $D = (D_1, D_2, \ldots, D_l)$.
- If $l = 1$, the process ends.
- Create a new sequence $E = (D_2, D_4, \ldots, D_{2 \lfloor l/2 \rfloor})$. In other words, $E$ is the sequence created by removing all odd-indexed elements from $D$.
- Change $D$ to $E$.
When this process terminates, the sequence $D$ contains only one number. You have to find this number.

-----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 last remaining number.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le N \le 10^{18}$

-----Subtasks-----
Subtask #1 (20 points):
- $1 \le T \le 10^5$
- $1 \le N \le 10^7$
Subtask #2 (80 points): original constraints

-----Example Input-----
1
9

-----Example Output-----
3

-----Explanation-----
Example case 1: The first $N$ Fibonacci numbers are $(0, 1, 1, 2, 3, 5, 8, 13, 21)$. The sequence $D$ is $(0, 1, 1, 2, 3, 5, 8, 3, 1) \rightarrow (1, 2, 5, 3) \rightarrow (2, 3) \rightarrow (3)$.

Source: codechef | Difficulty: MEDIUM
Tags: Bit manipulation

Mathematics


Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	s = len(str(bin(n))) - 3
	l = [2, 3, 0, 9]
	if s == 0:
		print('0')
	elif s == 1:
		print('1')
	elif s >= 2:
		a = s - 2
		print(l[a % 4])


import math
t = int(input())
a = [-1, 0, 1]
for i in range(61):
	temp = a[-1] + a[-2]
	temp = temp % 10
	a.append(temp)
for _ in range(t):
	n = int(input())
	n = int(math.log(n, 2))
	n = 2 ** n % 60
	print(a[n])


from collections import Counter
time = 60
fib = [0] * (time + 1)
fib[0] = 0
fib[1] = 1
for i in range(2, time + 1):
	fib[i] = fib[i - 1] + fib[i - 2]
	fib[i] %= 10
t = int(input())
for _ in range(t):
	n = int(input())
	most_pos = len(bin(n)[2:])
	pos = pow(2, most_pos - 1, time) - 1
	ans = fib[pos]
	print(ans)


T = int(input())
fib = []
ans = 0
a = 0
b = 1
i = 1
p = 10 ** 18
while i <= 60:
	fib.append(a)
	(a, b) = (b, a + b)
	i = i + 1

def binpow(x, p):
	if p == 0:
		return 1
	if p == 1:
		return x
	if p % 2 == 0:
		half = binpow(x, p // 2)
		return half * half
	else:
		half = binpow(x, p // 2)
		return half * half * x
for tc in range(T):
	n = int(input())
	import math
	k = math.floor(math.log(n, 2))
	at = 0
	st = n
	rt = st - at
	while rt >= 0:
		at = at + 1
		rt = st - 2 ** at
	bt = at - 1
	c = binpow(2, bt)
	print(fib[(c - 1) % 60] % 10)


t = int(input())
for j in range(t):
	n = int(input())
	r = len(bin(n)) - 3
	index = 2 ** r - 1
	if index == 0:
		print(0)
	elif index == 1:
		print(1)
	elif index % 10 == 3:
		print(2)
	elif index % 10 == 7:
		print(3)
	elif index % 10 == 1:
		print(9)
	elif index % 10 == 5:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	p2 = len(str(bin(n))) - 3
	a = [2, 3, 0, 9]
	if p2 >= 2:
		p2 = (p2 - 2) % 4
		print(a[p2])
	elif p2 == 1:
		print('1')
	else:
		print('0')


tsc = int(input())
for i in range(0, tsc):
	s = int(input())
	a = 0
	r = s - a
	while r >= 0:
		a = a + 1
		r = s - 2 ** a
	b = a - 1
	if b == 1:
		print(1)
	elif b % 4 == 2:
		print(2)
	elif b % 4 == 3:
		print(3)
	elif b % 4 == 0:
		print(0)
	elif b % 4 == 1:
		print(9)


import math

def MakePisanoCycle(m):
	f1 = 0
	f2 = 1
	f3 = 0
	count = 0
	Sequence = []
	first = True
	while not (f2 == 1 and f1 == 0 and (not first)):
		first = False
		Sequence.append(f1)
		f3 = (f2 + f1) % m
		f1 = f2
		f2 = f3
		count += 1
	return (Sequence, count)

def getLogNIndex(N):
	str1 = bin(N)
	p = len(str1) - bin(N).find('1')
	return 2 ** (p - 1)

def getSpecialArrayItem(N):
	N = getLogNIndex(N)
	index = (N - 1) % MODM
	return ThePisanoArray[index]
(ThePisanoArray, MODM) = MakePisanoCycle(10)
for _ in range(int(input())):
	N = int(input())
	print(getSpecialArrayItem(N))


k = [0] * 100
k[0] = 0
k[1] = 1
for i in range(2, 60):
	k[i] = k[i - 1] + k[i - 2]
for i in range(int(input())):
	inputNumber = int(input())
	msb = 0
	while inputNumber > 0:
		msb += 1
		inputNumber = inputNumber >> 1
	pos = pow(2, msb - 1) % 60
	print(k[pos - 1] % 10)


from math import *

def pisanoPeriod():
	p = [-1, 0, 1]
	for i in range(58):
		t = (p[-2] + p[-1]) % 10
		p.append(t)
	return p
R = lambda : list(map(int, input().split()))
p = pisanoPeriod()
for _ in range(int(input())):
	n = int(input())
	n = len(bin(n)) - 3
	n = 2 ** n
	n = n % 60
	print(p[n])


for _ in range(int(input())):
	n = int(input())
	p = len(str(bin(n))) - 3
	l = [2, 3, 0, 9]
	if p == 0:
		print('0')
	elif p == 1:
		print('1')
	elif p >= 2:
		a = p - 2
		print(l[a % 4])


for i in range(int(input())):
	n = int(input())
	l = len(str(bin(n))) - 3
	index = 2 ** l - 1
	if index == 0:
		print('0')
	elif index == 1:
		print('1')
	elif index % 10 == 3:
		print('2')
	elif index % 10 == 7:
		print('3')
	elif index % 10 == 5:
		print('0')
	elif index % 10 == 1:
		print('9')


T = int(input())
for tc in range(0, T):
	N = int(input())
	x = len(str(bin(N))) - 3
	dp = [2, 3, 0, 9]
	if x == 0:
		print(0)
	elif x == 1:
		print(1)
	else:
		a = x - 2
		print(dp[a % 4])


def fib(n):
	i = -1
	while n > 0:
		i += 1
		n = n // 2
	return i
fl = [0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1]
t = int(input())
for _ in range(t):
	n = int(input())
	d = 2 ** fib(n) % 60
	print(fl[d - 1])


fib = [1] * 61
fib[0] = 0
for i in range(2, 61):
	fib[i] = (fib[i - 1] + fib[i - 2]) % 10
for _ in range(int(input())):
	n = int(input())
	q = 1
	while n >= q:
		q <<= 1
	q >>= 1
	print(fib[q % 60 - 1])


def f(n):
	i = -1
	while n > 0:
		i += 1
		n = n // 2
	return i
fo = [0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1]
l = int(input())
for _ in range(l):
	n = int(input())
	d = 2 ** f(n) % 60
	print(fo[d - 1])


import math

def make_pisano_cycle(m):
	f1 = 0
	f2 = 1
	f3 = 0
	count = 0
	fib_series = []
	first = True
	while not (f2 == 1 and f1 == 0 and (not first)):
		first = False
		fib_series.append(f1)
		f3 = (f2 + f1) % m
		f1 = f2
		f2 = f3
		count += 1
	return (fib_series, count)

def get_log_n_index(n):
	str1 = bin(n)
	p = len(str1) - bin(n).find('1')
	return 2 ** (p - 1)

def get_special_array_item(n):
	n = get_log_n_index(n)
	index = (n - 1) % modm
	return the_pisano_array[index]
(the_pisano_array, modm) = make_pisano_cycle(10)
for i in range(int(input())):
	n = int(input())
	print(get_special_array_item(n))


import math
for i in range(int(input())):
	N = int(input())
	i = 1
	while 2 * i <= N:
		i *= 2
	val = i % 60
	a = 0
	b = 1
	for i in range(0, val):
		if i == val - 1:
			print(a)
		c = (a + b) % 10
		a = b
		b = c


a = int(input())
while a > 0:
	t = int(input())
	i = 1
	while 2 * i <= t:
		i *= 2
	value = 60
	t = i % value
	if t == 0:
		t = value
	if t == 1:
		print(0)
	elif t == 2:
		print(1)
	else:
		(p, q) = (0, 1)
		for i in range(t - 1):
			(p, q) = (q, (p + q) % 10)
		print(p % 10)
	a -= 1


import math
a = [-1, 0, 1]
for i in range(58):
	temp = a[-1] + a[-2]
	temp = temp % 10
	a.append(temp)
for _ in range(int(input())):
	n = int(input())
	temp = len(bin(n)) - 3
	temp = 2 ** temp
	temp = temp % 60
	print(a[temp])


fibb = [0, 0, 1]
for i in range(58):
	fibb.append((fibb[-1] + fibb[-2]) % 10)
fibb[0] = fibb[-1]

def solve(x):
	t = 2 ** (x.bit_length() - 1) % 60
	print(fibb[t])
n = int(input())
for i in range(n):
	x = int(input())
	solve(x)


def fibb(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	else:
		return fibb(num - 1) + fibb(num - 2)
t = int(input())
while t != 0:
	n = int(input())
	x = str(bin(n).replace('0b', ''))
	if len(x) == 1:
		print('0')
	elif len(x) == 2:
		print('1')
	else:
		c = len(x) % 4
		if c == 0:
			print('3')
		elif c == 1:
			print('0')
		elif c == 2:
			print('9')
		else:
			print('2')
	t -= 1


from bisect import bisect_left, bisect_right
import math
from sys import maxsize
from collections import defaultdict
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]

def findlog(p):
	x = 0
	while p != 0:
		x += 1
		p //= 2
	return x - 1
f = [0, 1]
for i in range(2, 61):
	f.append((f[i - 1] + f[i - 2]) % 10)
for _ in range(ii()):
	print(f[int((2 ** findlog(ii()) - 1) % 60)])


t = int(input())
while t > 0:
	n = int(input())
	i = 1
	while 2 * i <= n:
		i *= 2
	val = 60
	n = i % val
	if n == 0:
		n = val
	if n == 1:
		print(0)
	elif n == 2:
		print(1)
	else:
		(a, b) = (0, 1)
		for i in range(n - 1):
			(a, b) = (b, (a + b) % 10)
		print(a % 10)
	t -= 1


import math
F = [0, 1]

def generateFibonacci():
	for i in range(60):
		F.append((F[-1] + F[-2]) % 10)
tc = int(input())
generateFibonacci()
for _ in range(tc):
	n = int(input())
	n = n >> 1
	n = n | n >> 32
	n = n | n >> 16
	n = n | n >> 8
	n = n | n >> 4
	n = n | n >> 2
	n = n | n >> 1
	n %= 60
	print(F[n])


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	for i in range(61):
		if 1 << i >= n:
			break
	if n & n - 1 != 0:
		i -= 1
	n = 1 << i
	a = [-1] * 61
	a[1] = 0
	a[2] = 1
	for i in range(3, 61):
		a[i] = (a[i - 1] + a[i - 2]) % 10
	n = n % 60
	if n == 0:
		n = 60
	print(a[n])


import sys
for x in range(int(input())):
	n = int(sys.stdin.readline())
	r = len(bin(n)) - 3
	index = 2 ** r - 1
	if index == 0:
		print(0)
	elif index == 1:
		print(1)
	elif index % 10 == 3:
		print(2)
	elif index % 10 == 7:
		print(3)
	elif index % 10 == 1:
		print(9)
	elif index % 10 == 5:
		print(0)


import math
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n == 2 or n == 3:
		print(1)
	else:
		f = [2, 3, 0, 9]
		print(f[(len(bin(n)) - 3) % 4 - 2])


def fib2(n):
	l = [0, 1]
	for i in range(2, n + 1):
		l[i % 2] = l[0] + l[1]
	return l[n % 2]
t = int(input())
for i in range(t):
	n = int(input())
	l = []
	idx = 2 ** (len(bin(n)[2:]) - 1) - 1
	print(fib2(idx % 60) % 10)


import math

def p_two(n):
	return int(math.log(n, 2))

def f(n):
	a = [0, 1]
	r = [0, 1]
	i = 2
	while i < n:
		a += [(a[-1] + a[-2]) % 10]
		i += 1
	return a
for x in range(int(input())):
	n = int(input())
	r = len(bin(n)) - 3
	index = 2 ** r - 1
	if index == 0:
		print(0)
	elif index == 1:
		print(1)
	elif index % 10 == 3:
		print(2)
	elif index % 10 == 7:
		print(3)
	elif index % 10 == 1:
		print(9)
	elif index % 10 == 5:
		print(0)


import math

def r(n):
	cycle = 60
	index = (1 << len(bin(n)) - 3) % cycle
	cur = 0
	next = 1
	for i in range(1, index):
		nextNext = (cur + next) % 10
		cur = next
		next = nextNext
	return cur
t = int(input())
for i in range(t):
	c = int(input())
	print(r(c))


xd = [2, 3, 0, 9]
for _ in range(int(input())):
	n = int(input())
	n = len(bin(n)) - 3
	if n == 0:
		print(0)
	elif n == 1:
		print(1)
	else:
		n -= 2
		print(xd[n % 4])


t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	k = len(str(bin(n))) - 3
	l = [2, 3, 0, 9]
	if k == 0:
		print(0)
	elif k == 1:
		print(1)
	else:
		a = k - 2
		print(l[a % 4])


import math

def r(n):
	cycle = 60
	index = (1 << int(math.floor(math.log2(n)))) % cycle
	cur = 0
	next = 1
	for i in range(1, index):
		nextNext = (cur + next) % 10
		cur = next
		next = nextNext
	return cur
t = int(input())
for i in range(t):
	c = int(input())
	print(r(c))


fl = [0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1]

def log2(num):
	i = -1
	while num > 0:
		i += 1
		num //= 2
	return i
cycle = 60
for _ in range(int(input())):
	n = int(input())
	target = 2 ** log2(n) % 60
	print(fl[target - 1])


import math

def logBase2(n):
	res = 0
	fact = 1
	while fact << res + 1 <= n:
		res += 1
	return res
t = int(input())
a = [-1, 0, 1]
for i in range(58):
	temp = a[-1] + a[-2]
	temp = temp % 10
	a.append(temp)
for _ in range(t):
	n = int(input())
	n = 1 << logBase2(n)
	print(a[n % 60])


t = int(input())
for i in range(t):
	n = int(input())
	x = len(str(bin(n))) - 3
	(a, b) = (0, 1)
	for j in range(60):
		if j == (2 ** x - 1) % 60:
			print(a % 10)
		tmp = a + b
		a = b
		b = tmp


given = []
for _ in range(int(input())):
	n = int(input())
	given.append(n)
fib = [0, 1]
for i in range(60):
	fib.append((fib[-1] + fib[-2]) % 10)
l1 = [1, 2]
l2 = [0, 1]
x = 2
for i in range(600):
	l1.append(l1[-1] * 2)
	l2.append(l2[-1] + x)
	x = x + x
for ele in given:
	for i in range(len(l1) - 1):
		if l1[i] <= ele < l1[i + 1]:
			print(fib[l2[i] % 60])
			break


fb = [0, 1]
for i in range(1, 60):
	fb.append(fb[i - 1] + fb[i])
for _ in range(int(input())):
	n = int(input())
	c = 1
	while n > 1:
		n //= 2
		c *= 2
	print(fb[c % 60 - 1] % 10)


import math

def fib(n):
	if n < 2:
		return n
	dp = [0] * (n + 1)
	dp[1] = 1
	for i in range(2, n + 1):
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10
	return dp[n]
t = int(input())
for _ in range(t):
	n = int(input())
	exp = int(math.floor(math.log(n, 2)))
	arg = (2 ** exp - 1) % 60
	print(fib(arg))


T = int(input())
for i in range(T):
	n = int(input())
	i = 1
	while 2 * i <= n:
		i *= 2
	value = 60
	n = i % value
	if n == 0:
		n = value
	if n == 1:
		print(0)
	elif n == 2:
		print(1)
	else:
		(a, b) = (0, 1)
		for i in range(n - 1):
			(a, b) = (b, (a + b) % 10)
		print(a % 10)


t = int(input())
while t != 0:
	n = int(input())
	x = str(bin(n).replace('0b', ''))
	if len(x) == 1:
		print('0')
	elif len(x) == 2:
		print('1')
	else:
		c = len(x) % 4
		if c == 0:
			print('3')
		elif c == 1:
			print('0')
		elif c == 2:
			print('9')
		else:
			print('2')
	t -= 1


def fib(n):
	index = -1
	while n > 0:
		index += 1
		n = n // 2
	return index
first60Sequence = [0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1]
test = int(input())
for i in range(test):
	number = int(input())
	respectiveIndex = 2 ** fib(number) % 60
	print(first60Sequence[respectiveIndex - 1])


import math

def fib(f, n):
	f[0] = 0
	f[1] = 1
	for i in range(2, n + 1):
		f[i] = (f[i - 1] + f[i - 2]) % 10
	return f

def findLastDigit(n):
	f = [0] * 61
	f = fib(f, 60)
	return f[n % 60]

def func(n):
	k = n
	c = 0
	while k > 1:
		k = k // 2
		c += 1
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	k = func(n)
	last_num = 2 ** k
	print(findLastDigit(last_num - 1))


t = int(input())
for i in range(t):
	n = int(input())
	x = len(str(bin(n).replace('0b', '')))
	if x == 1:
		print(0)
	elif x == 2:
		print(1)
	elif x % 4 == 0:
		print(3)
	elif x % 4 == 1:
		print(0)
	elif x % 4 == 2:
		print(9)
	elif x % 4 == 3:
		print(2)


from math import log2, floor
fibs = [0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1]
for _ in range(int(input())):
	n = int(input())
	i = len(str(bin(n))) - 3
	print(fibs[(2 ** i - 1) % 60])