Read problems statements in Mandarin Chinese  and Russian. 

Aditi recently discovered a new magic trick. First, she gives you an integer N and asks you to think an integer between 1 and N. Then she gives you a bundle of cards each having a sorted list (in ascending order) of some distinct integers written on it. The integers in all the lists are between 1 and N. Note that the same integer may appear in more than one card. Now, she shows you these cards one by one and asks whether the number you thought is written on the card or not. After that, she immediately tells you the integer you had thought of.
Seeing you thoroughly puzzled, she explains that she can apply the trick so fast because she is just adding the first integer written on the cards that contain the integer you had thought of, and then gives the sum as the answer. She calls a bundle interesting if when the bundle is lexicographically sorted, no two consecutive cards have any number in common. Now she challenges you to find out the minimum number of cards she will need for making an interesting bundle such that the magic trick will work every time.

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

The first line of the input contains an integer T denoting the number of test cases.		
Each test case contains a line with a single integer N.
 
------ Output ------ 

For each test case, output a line containing a single integer denoting the minimum number of cards required.

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

1 ≤ T ≤ 10^{5}
1 ≤ N ≤ 10^{18}

------ Sub tasks ------ 

Subtask #1: 1 ≤ T ≤ 10, 1 ≤ N ≤ 10 (5 points)
Subtask #2: 1 ≤ T ≤ 100, 1 ≤ N ≤ 1000 (10 points)
Subtask #3: Original Constraints (85 points)

----- Sample Input 1 ------ 
2
1
4
----- Sample Output 1 ------ 
1
3
----- explanation 1 ------ 

In example 1, only 1 card containing {1} will work.
In example 2, make 3 cards containing {1,4}, {2} and {3,4}.

Assume you thought of 1, then you will select the 1st card {1,4}, then she will correctly figure out the integer you thought being 1.
Assume you thought of 2, then you will select the 2nd card {2}, then she will correctly figure out the integer you thought being 2.
Assume you thought of 3, then you will select the 3rd card {3,4}, then she will correctly figure out the integer you thought being 3.
Assume you thought of 4, then you will select 1st card {1,4} and 3rd card {3,4}, then she will calculate the sum of the first integers of the two card 1 + 3 = 4, and she will answer it.

Thus her trick will work well in every case. And we can check it easily that the cards are sorted in lexicographical order and two consecutive cards have no common integers.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
T = int(input().strip())

def gen_fib(N):
	if N <= 3:
		return N
	else:
		fib = []
		fib.append(0)
		fib.append(1)
		fib.append(2)
		i = 2
		while fib[i] <= N:
			fib.append(fib[i] + fib[i - 1])
			i += 1
		return i - 1
while T > 0:
	N = int(input().strip())
	print(gen_fib(N))
	T -= 1


t = int(input(''))
a = [1, 2]
i = 1
while a[i] <= 10 ** 18:
	a.append(a[i] + a[i - 1])
	i += 1
for i in range(t):
	n = int(input(''))
	j = 0
	while j < len(a):
		if a[j] == n:
			print(j + 1)
			break
		elif a[j] > n:
			print(j)
			break
		j += 1


a = int(input())
d = []
for i in range(a):
	b = int(input())
	c = 1
	m = 1
	i = 1
	while c < b:
		i += 1
		n = c + 1
		c += m
		m = n
	d.append(i)
for i in range(a):
	print(d[i])


import math
n = int(input())
while n != 0:
	n -= 1
	ip = int(input())
	if ip == 1:
		print('1')
		continue
	elif ip == 2:
		print('2')
		continue
	f = 1
	s = 2
	ans = 2
	t = f + s
	while ip >= t:
		f = s
		s = t
		t = f + s
		ans += 1
	print(ans)


t = int(input())
for it in range(t):
	n = int(input())
	s1 = 1
	s2 = 2
	count = 2
	while n >= s1 + s2:
		count += 1
		t = s2
		s2 = s1 + s2
		s1 = t
	if n == 1:
		print(n)
	else:
		print(count)


t = int(input())
while t != 0:
	n = int(input())
	i = 1
	k = 1
	l = 2
	j = 1
	while l <= n:
		i = k
		k = l
		l = i + k
		j = j + 1
	print(j)
	t = t - 1


A = [0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 39088168, 63245985, 102334154, 165580140, 267914295, 433494436, 701408732, 1134903169, 1836311902, 2971215072, 4807526975, 7778742048, 12586269024, 20365011073, 32951280098, 53316291172, 86267571271, 139583862444, 225851433716, 365435296161, 591286729878, 956722026040, 1548008755919, 2504730781960, 4052739537880, 6557470319841, 10610209857722, 17167680177564, 27777890035287, 44945570212852, 72723460248140, 117669030460993, 190392490709134, 308061521170128, 498454011879263, 806515533049392, 1304969544928656, 2111485077978049, 3416454622906706, 5527939700884756, 8944394323791463, 14472334024676220, 23416728348467684, 37889062373143905, 61305790721611590, 99194853094755496, 160500643816367087, 259695496911122584, 420196140727489672, 679891637638612257, 1100087778366101930, 1779979416004714188, 2880067194370816119]
a = int(input())
while a > 0:
	a -= 1
	b = int(input())
	c = 0
	for i in range(1, 89):
		if b <= A[i]:
			c = i
			break
	print(c)


from math import log
phi = (1 + 5 ** 0.5) / 2

def fibinv(f):
	if f < 2:
		return f
	return int(round(log(f * 5 ** 0.5) / log(phi)))

def mul(A, B):
	(a, b, c) = A
	(d, e, f) = B
	return (a * d + b * e, a * e + b * f, b * e + c * f)

def pow(A, n):
	if n == 1:
		return A
	if n & 1 == 0:
		return pow(mul(A, A), n // 2)
	else:
		return mul(A, pow(mul(A, A), (n - 1) // 2))

def fib(n):
	if n < 2:
		return n
	return pow((1, 1, 0), n - 1)[0]

class MagicTrick(object):

	def GetMinCards2(self, N):
		if N == 1:
			return 1
		steps = fibinv(N)
		exact_fib = fib(steps)
		while exact_fib > N:
			steps -= 1
			exact_fib = fib(steps)
		return steps - 1

def main():
	magic_trick = MagicTrick()
	T = int(input())
	results = []
	for t in range(T):
		N = int(input())
		result2 = magic_trick.GetMinCards2(N)
		results.append(result2)
	for t in range(T):
		print(results[t])
main()


def relsearch(a, x, p=0, reverse=False):
	l = len(a)
	if l == 0:
		return 0
	if l == 1:
		if x < a[0]:
			return 0
		else:
			return 1
	else:
		i = l // 2
		if a[i - 1] <= x and a[i] > x:
			return i
		elif not a[i - 1] <= x:
			return relsearch(a[:i], x, p)
		else:
			return i + relsearch(a[i:], x, i)
import sys
input = sys.stdin.readline
f = [1, 2]
while f[-1] <= 10 ** 18:
	f.append(f[-1] + f[-2])
tests = int(input())
for t in range(tests):
	print(relsearch(f, int(input())))


a = []
a.append(1)
a.append(1)
a.append(2)
for i in range(3, 90):
	a.append(a[i - 1] + a[i - 2])
for i in range(int(input())):
	n = int(input())
	for i in range(1, 90):
		if a[i] >= n:
			break
	if a[i] == n:
		print(i)
	else:
		print(i - 1)


import sys
input()
for i in sys.stdin:
	i = int(i.rstrip())
	fib = 2
	(n1, n2) = (1, 1)
	count = 1
	while fib <= i:
		(n1, n2) = (n2, fib)
		fib = n1 + n2
		count += 1
	print(count)


t = int(input())
if 1 <= t <= 10 ** 6:
	for i in range(0, t, 1):
		n = int(input())
		if 1 <= n <= 10 ** 18:
			sum = 0
			a = 0
			b = 1
			c = 0
			while sum < n:
				c = c + 1
				sum = sum + b
				temp = b
				b = b + a
				a = temp
			print(c)


def allfib(n):
	a = 1
	b = 2
	arr = [1, 2]
	c = 0
	while c < n:
		c = a + b
		arr.append(c)
		a = b
		b = c
	return arr
t = int(input())
arr = allfib(pow(10, 18) + 1)
for i in range(1, t + 1):
	n = int(input())
	i = 0
	while arr[i] <= n:
		i += 1
	print(i)


import math
series = []
a = 0
sum = 1
while sum < 1000000000000000000:
	temp = a + sum
	a = sum
	sum = temp
	series.append(sum)
t = int(input())
for it in range(t):
	n = int(input())
	for i in range(len(series)):
		if n == series[i]:
			i = i + 1
			break
		elif n < series[i]:
			break
	print(i)


import math
fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931]
for T in range(int(input())):
	n = int(input())
	for i in range(len(fib)):
		if fib[i] > n:
			print(i)
			break


def fibonacci():
	for n in range(4, 90):
		ans = 0
		ans = int(L[n - 2] + L[n - 3])
		L.append(ans)

def findAns(n):
	i = 1
	if n < 4:
		return n
	while L[i + 1] < n and i < 90:
		i += 1
		if L[i + 1] == n:
			i += 1
	return i + 1
T = int(input(''))
L = [1, 2, 3]
fibonacci()
for i in range(T):
	n = int(input(''))
	print(findAns(n))


HemC = [1, 1]
i = 2
SIZE = 10 ** 18 + 1
while HemC[i - 1] < SIZE:
	HemC.append(HemC[i - 1] + HemC[i - 2])
	i += 1
N = i

def lookup(x):
	ans = 0
	while HemC[ans] <= x:
		ans += 1
	return ans
for i in range(int(input())):
	n = int(input())
	ans = lookup(n) - 1
	print(ans)


T = int(input())
while T != 0:
	N = int(input())
	a = 1
	b = 1
	c = 1
	counter = 0
	while c <= N:
		a = b
		b = c
		c = a + b
		counter += 1
	print(counter)
	T -= 1


arr = [1, 1]
uplim = 10 ** 18
while arr[-1] <= uplim:
	arr.append(arr[-1] + arr[-2])
import bisect
t = int(input())
for it in range(t):
	n = int(input())
	x = bisect.bisect(arr, n) - 1
	print(x)


for _ in range(int(input())):
	n = int(input())
	if n < 3:
		k = n
	else:
		f1 = 1
		f2 = 2
		k = 2
		while True:
			f3 = f1 + f2
			k += 1
			if n < f3 + f2:
				break
			f1 = f2
			f2 = f3
	print(k)


n = int(input())
for x in range(n):
	num = int(input())
	x = 0
	p = 1
	t = p + x
	k = -1
	while t <= num:
		t = p + x
		x = p
		p = t
		k += 1
	print(k)


fibo = [1, 1]
for i in range(2, 100):
	fibo.append(fibo[i - 1] + fibo[i - 2])
t = int(input())
while t:
	t -= 1
	n = int(input())
	i = 0
	while fibo[i] <= n:
		i += 1
	print(i - 1)


f = [1, 2]
for i in range(2, 100):
	f.append(f[i - 1] + f[i - 2])
for i in range(int(input())):
	(x, ind) = (int(input()), 0)
	for j in range(len(f)):
		if f[j] > x:
			ind = j
			break
	print(j)


fib = [1, 2]
while fib[len(fib) - 1] < 10 ** 18:
	i = len(fib)
	fib.append(fib[i - 1] + fib[i - 2])
t = int(input())
for i in range(0, t):
	n = int(input())
	index = 0
	while fib[index] <= n:
		index += 1
	print(index)


t = int(input())
while t > 0:
	n = int(input())
	c = 0
	b = 1
	m = 1
	while m <= n:
		u = m
		m = m + b
		b = u
		c += 1
	print(c)
	t = t - 1


l = [1, 2]

def calc(n):
	if n <= l[-1]:
		i = -1
		while n < l[i]:
			i -= 1
		return i + len(l) + 1
	else:
		while n > l[-1]:
			l.append(l[-2] + l[-1])
		return calc(n)
t = int(input())
while t > 0:
	n = int(input())
	ans = calc(n)
	print(ans)
	t -= 1


numbers = [1, 2]
num = 0
while num < pow(10, 19):
	num = numbers[-1] + numbers[-2]
	numbers.append(num)
l = int(input())
for i in range(l):
	num = int(input())
	for (index, fib) in enumerate(numbers):
		if fib > num:
			print(index)
			break


def fib(n):
	a = 0
	b = 1
	ctr = 1
	sm = a + b
	s = 0
	while 1:
		s += sm
		if n <= s:
			print(ctr)
			break
		sm = a + b
		a = b
		b = sm
		ctr += 1
t = int(input())
while t != 0:
	n = int(input())
	fib(n)
	t -= 1


list = [1, 2]
for i in range(90):
	list.append(list[i] + list[i + 1])
t = int(input())
for i in range(t):
	n = int(input())
	j = 0
	while list[j] <= n:
		j += 1
	print(j)


import sys
import math

def cannot_be_written(num, base):
	bool = True
	basis_used = len(base) - 1
	if basis_used > 0:
		biggest_possible = base[basis_used]
		num -= biggest_possible
		while num > 0 and basis_used > 0:
			basis_used -= 1
			try_subtracting = True
			while try_subtracting and basis_used > 0:
				basis_used -= 1
				biggest_possible = base[basis_used]
				try_subtracting = num - biggest_possible < 0
			if basis_used >= 0:
				num -= biggest_possible
		bool = num != 0
	return bool

def n_cards_for(int_n):
	base = []
	for num in range(int_n):
		num += 1
		if cannot_be_written(num, base):
			base.append(num)
	n_cards = len(base)
	return n_cards

def main():
	lines = sys.stdin.readlines()
	n_cases = int(lines[0])
	for i in range(n_cases):
		line = lines[i + 1]
		int_n = int(line)
		n_cards = n_cards_for(int_n)
		print(n_cards, end='\n')

def fibonacci_up_to_pow_long(pow_of_ten):
	series = [0]
	new_n = 1
	series.append(new_n)
	max_lim = 10 ** pow_of_ten
	while new_n < max_lim:
		new_n = series[-1] + series[-2]
		series.append(new_n)
	return series

def n_cards_fibo_long(int_n, fibo_series):
	n_cards = 0
	for (n_cards, fibo_int) in enumerate(fibo_series):
		if fibo_int > int_n:
			break
	return n_cards - 2

def fibonacci_up_to_pow_str(pow_of_ten):
	series = []
	return series

def n_cards_fibo_str(int_n, fibo_series):
	n_cards = 0
	return n_cards

def main_fibo():
	lines = sys.stdin.readlines()
	n_cases = int(lines[0])
	fibo_series_long = fibonacci_up_to_pow_long(38)
	for i in range(n_cases):
		int_str = lines[i + 1]
		int_long = int(int_str)
		n_cards = n_cards_fibo_long(int_long, fibo_series_long)
		print(n_cards, end='\n')
main_fibo()


t = int(input())
while t:
	t -= 1
	n = int(input())
	if n == 1:
		print(1)
		continue
	elif n == 2:
		print(2)
		continue
	else:
		count = 2
		(a, b, c) = (1, 2, 3)
		while a + b <= n:
			count += 1
			(a, b) = (b, a + b)
		print(count)


num = int(input())
arr = [0] * num
for i in range(num):
	arr[i] = int(input())
maxx = max(arr)
fib = []
fib.append(1)
a = 1
b = 1
c = 2
while c <= maxx:
	fib.append(c)
	a = b
	b = c
	c = a + b
fib.append(c)
for i in range(num):
	x = arr[i]
	j = 0
	while fib[j] <= x:
		j += 1
	print(j)


f = [0, 1]
while f[-1] <= 10 ** 20:
	f.append(f[-1] + f[-2])
for c in range(int(input())):
	n = int(input())
	c = 1
	while f[c + 2] <= n:
		c += 1
	print(c)


fib = [1, 2]
i = 1
while fib[i] <= 10 ** 18:
	fib.append(fib[i] + fib[i - 1])
	i += 1

def search(x):
	for i in range(len(fib) - 1):
		if fib[i] <= x < fib[i + 1]:
			return i
	return len(fib) - 1
for tests in range(int(input())):
	n = int(input())
	print(1 + search(n))


fib = [0]
(a, b) = (1, 1)
while b < 10 ** 19:
	fib.append(b)
	(a, b) = (b, a + b)
for t in range(int(input())):
	n = int(input())
	for i in range(len(fib)):
		if fib[i] >= n:
			if fib[i] == n:
				print(i)
			else:
				print(i - 1)
			break


class MatrixFibonacci:
	Q = [[1, 1], [1, 0]]

	def __init__(self):
		self.__memo = {}

	def __multiply_matrices(self, M1, M2):
		a11 = M1[0][0] * M2[0][0] + M1[0][1] * M2[1][0]
		a12 = M1[0][0] * M2[0][1] + M1[0][1] * M2[1][1]
		a21 = M1[1][0] * M2[0][0] + M1[1][1] * M2[1][0]
		a22 = M1[1][0] * M2[0][1] + M1[1][1] * M2[1][1]
		r = [[a11, a12], [a21, a22]]
		return r

	def __get_matrix_power(self, M, p):
		if p == 1:
			return M
		if p in self.__memo:
			return self.__memo[p]
		K = self.__get_matrix_power(M, int(p / 2))
		R = self.__multiply_matrices(K, K)
		self.__memo[p] = R
		return R

	def get_number(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		powers = [int(pow(2, b)) for (b, d) in enumerate(reversed(bin(n - 1)[2:])) if d == '1']
		matrices = [self.__get_matrix_power(MatrixFibonacci.Q, p) for p in powers]
		while len(matrices) > 1:
			M1 = matrices.pop()
			M2 = matrices.pop()
			R = self.__multiply_matrices(M1, M2)
			matrices.append(R)
		return matrices[0][0][0]
mfib = MatrixFibonacci()
numbers = []
num = 1
count = 3
while num < pow(10, 19):
	numbers.append(num)
	num = mfib.get_number(count)
	count += 1
l = int(input())
for i in range(l):
	num = int(input())
	for (index, fib) in enumerate(numbers):
		if fib > num:
			print(index)
			break


fib = [1, 1]
for i in range(100):
	fib.append(fib[-1] + fib[-2])
from bisect import bisect_left as bl
for _ in range(int(input())):
	n = int(input())
	ind = bl(fib, n)
	if n == 1:
		print(1)
	else:
		i = 0
		while i < 100 and fib[i] <= n:
			ans = fib[i]
			i += 1
		print(i - 1)


from math import log, sqrt
fib = [0] * 100
fib[0] = 0
fib[1] = 1
fib[2] = 2
for i in range(3, 93):
	fib[i] = fib[i - 1] + fib[i - 2]
for i in range(int(input())):
	n = int(input())
	for j in range(100):
		if fib[j] > n:
			print(j - 1)
			break
		elif fib[j] == n:
			print(j)
			break


def slv(n):
	f1 = 1
	f2 = 2
	order = 2
	while f2 < n:
		(f2, f1) = (f1 + f2, f2)
		order += 1
	if n < 2:
		return n
	if f2 > n:
		return order - 1
	else:
		return order
ntest = int(input())
for t in range(ntest):
	n = int(input())
	print(slv(n))


from math import floor, log, sqrt, ceil
phi = (1 + sqrt(5)) / 2

def f(n):
	a = [1, 2]
	while True:
		if a[-2] <= n < a[-1]:
			return len(a) - 1
		else:
			a.append(a[-1] + a[-2])
for test in range(int(input())):
	print(f(int(input())))


d = {-1: 0, 0: 1}
c = 1
f = 1
while f <= 10 ** 18:
	f = d[c - 1] + d[c - 2]
	d[c] = f
	c += 1
t = int(input())
for _ in range(t):
	n = int(input())
	c = 1
	while d[c] <= n:
		c += 1
	print(c - 1)


import sys

def generate_fib(fib):
	fib[1] = 1
	fib[2] = 2
	for i in range(3, len(fib)):
		fib[i] = fib[i - 1] + fib[i - 2]
	return

def solve(value, fib):
	i = 1
	while value > fib[i]:
		i += 1
	return i if fib[i] == value else i - 1
T = int(input())
fib = [0] * 100
generate_fib(fib)
for i in range(T):
	value = int(input())
	print(solve(value, fib))


theFibSeries = [1, 2]
while theFibSeries[-1] < 10 ** 20:
	theFibSeries.append(theFibSeries[-1] + theFibSeries[-2])
tCase = int(input())
for times in range(tCase):
	theNumTObeTested = int(input())
	thepossiblesolution = 0
	while theFibSeries[thepossiblesolution] <= theNumTObeTested:
		thepossiblesolution += 1
	print(thepossiblesolution)


import functools
from math import sqrt

def fib(n):
	a = b = 1
	for i in range(n):
		yield a
		(a, b) = (b, a + b)

def main():
	t = int(input())
	min_cards = []
	fibs = list(fib(90))
	for n in range(t):
		num = int(input())
		if num in fibs and num != 1:
			min_cards.append(fibs.index(num))
		elif num == 1:
			min_cards.append(1)
		else:
			card = next((x[0] for x in enumerate(fibs) if x[1] > num))
			min_cards.append(card - 1)
	print(*min_cards, sep='\n')
main()


Fib = [0, 1]
for i in range(100):
	Fib.append(Fib[-1] + Fib[-2])

def solve():
	n = int(input())
	ans = 0
	i = 0
	while Fib[i + 2] <= n:
		ans += 1
		i += 1
	print(ans)
t = int(input())
for i in range(t):
	solve()


me_list = []
a = 1
b = 1
while a <= pow(10, 18):
	(a, b) = (b, a + b)
	me_list.append(a)
T = int(input())
while T:
	N = int(input())
	count = 0
	if N == 1:
		print(1)
	else:
		for i in me_list:
			if N < i:
				break
			else:
				count = count + 1
		print(count)
	T = T - 1


a = [0, 1]
for i in range(2, 89):
	temp = a[i - 1] + a[i - 2]
	a.append(temp)
t = int(input())
for i in range(t):
	n = int(input())
	if n == 1 or n == 2:
		print(n)
	else:
		for j in range(3, 87):
			if n + 1 <= a[j + 2]:
				print(j)
				break