You are given n positive integers a_1, a_2, ..., a_{n}.

For every a_{i} you need to find a positive integer k_{i} such that the decimal notation of 2^{k}_{i} contains the decimal notation of a_{i} as a substring among its last min(100, length(2^{k}_{i})) digits. Here length(m) is the length of the decimal notation of m.

Note that you don't have to minimize k_{i}. The decimal notations in this problem do not contain leading zeros.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 2 000) — the number of integers a_{i}.

Each of the next n lines contains a positive integer a_{i} (1 ≤ a_{i} < 10^11).


-----Output-----

Print n lines. The i-th of them should contain a positive integer k_{i} such that the last min(100, length(2^{k}_{i})) digits of 2^{k}_{i} contain the decimal notation of a_{i} as a substring. Integers k_{i} must satisfy 1 ≤ k_{i} ≤ 10^50.

It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.


-----Examples-----
Input
2
8
2

Output
3
1

Input
2
3
4857

Output
5
20

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
from sys import stdin, exit
n = int(stdin.readline())
exp = 10
for _ in range(n):
	a = int(stdin.readline())
	p10 = 1
	e10 = 0
	while p10 <= a:
		p10 = p10 * 10
		e10 = e10 + 1
	b = 5 ** exp * a % 2 ** e10
	b = (2 ** e10 - b) % 2 ** e10
	if b % 5 == 0:
		b = b + 2 ** e10
	a = a * 10 ** exp + b * 2 ** exp
	e10 = e10 + exp
	ans = -1
	cur = 2 ** (e10 + 5)
	for dig in range(1, e10 + 1):
		step = 4 * 5 ** (dig - 2)
		if dig == 1:
			step = 1
		b = a % 10 ** dig
		for i in range(5):
			x = pow(2, cur, 10 ** dig)
			if b == x:
				break
			cur = cur + step
		else:
			break
	else:
		ans = cur
	print('{}'.format(ans))


import sys
import math
from decimal import *
line = lambda : list((int(x) for x in input().split()))

def pow(n, k, p):
	if k == 0:
		return 1 % p
	if k % 2 == 1:
		return pow(n, k - 1, p) * n % p
	t = pow(n, k / 2, p)
	return t * t % p
test = int(input())
for i in range(0, test):
	x = int(input())
	x = x * 10 ** 6
	x += (2 ** 17 - x % 2 ** 17) % 2 ** 17
	if x % 5 == 0:
		x += 2 ** 17
	res = 0
	for i in range(1, 17 + 1):
		while pow(2, res, 5 ** i) != x % 5 ** i:
			if i == 1:
				res += 1
			else:
				res += 4 * 5 ** (i - 2)
	res += 4 * 5 ** 16
	print(res)


LEN1 = 31
LEN2 = 50
MOD = 10 ** LEN2

def binpow(a, b, mod):
	x = 1
	y = a
	while b > 0:
		if b % 2:
			x = x * y % mod
		y = y * y % mod
		b //= 2
	return x

def solve(n):
	n = n * 10 ** LEN1
	diff = (2 ** LEN2 - n) % 2 ** LEN2
	if diff < 0:
		diff += 2 ** LEN2
	if diff % 5 == 0:
		diff += 2 ** LEN2
	n += diff
	n %= 5 ** LEN2
	k = 0
	for i in range(5):
		if 2 ** k % 5 == n % 5:
			break
		k += 1
	Pow = 1
	Pow2 = 2 ** k
	Pow25 = 2 ** 4
	for i in range(2, LEN2 + 1):
		res = n % (25 * Pow)
		for j in range(5):
			if Pow2 % (25 * Pow) == res:
				break
			k += 4 * Pow
			Pow2 *= Pow25
			Pow2 %= MOD
		if Pow2 % (25 * Pow) != res:
			print('bad\n')
		Pow *= 5
		Pow25 = Pow25 * Pow25 % MOD * Pow25 % MOD * Pow25 % MOD * Pow25 % MOD
	return k
n = int(input())
a = [int(input()) for i in range(n)]
for x in a:
	print(solve(x))


m10 = 10000000000
mp = 21
p2 = 2 ** mp

def qmd(log, md):
	ans = 1
	a = 2
	while log > 0:
		if log % 2:
			ans = ans * a % md
		log = log // 2
		a = a * a % md
	return ans
n = int(input())
for nn in range(n):
	a = int(input())
	x = a * m10 // p2 * p2 + p2
	while x % 5 == 0:
		x += p2
	log = 0
	while 2 ** log % 5 != x % 5:
		log += 1
	md = 5
	phi = 4
	for i in range(1, mp):
		md *= 5
		while qmd(log, md) != x % md:
			log += phi
		phi *= 5
	if log < mp:
		log += phi
	print(log)


import sys
import random
N = 20
ntest = int(sys.stdin.readline())
for _ in range(ntest):
	target = int(sys.stdin.readline())
	divtarget = 2 ** N
	target_min = target
	target_max = target + 1
	while True:
		target_min *= 10
		target_max *= 10
		if target_min // divtarget == (target_max - 1) // divtarget:
			continue
		target = (target_max - 1) // divtarget
		if target % 5 == 0:
			target -= 1
		target *= divtarget
		if target >= target_min:
			break
	mod = 10 ** 0
	base = N
	gap = 1
	for i in range(100):
		mod *= 10
		target_mod = target % mod
		cur = pow(2, base, mod)
		cur_mul = pow(2, gap, mod)
		while cur != target_mod:
			base += gap
			cur = cur * cur_mul % mod
		newgap = gap
		base += gap
		cur = pow(2, base, mod)
		while cur != target_mod:
			base += gap
			newgap += gap
			cur = cur * cur_mul % mod
		gap = newgap
		if mod > target:
			break
	print(base)


def F(x):
	if x == 0:
		return 0
	return F(x // 10) + 1

def mul(x, num):
	return pow(2, x, 10 ** num)
ml = 1000000

def solveS(x):
	ln = F(x * ml)
	f = 1 << ln
	s = (x * ml + f - 1) // f * f
	while s % 5 == 0:
		s += f
	return s

def solveNK(s, n, r, q):
	for i in range(0, 6):
		if mul(r + i * q, n) == s:
			return r + i * q

def solveK(s):
	n = F(s)
	last = s % 10
	for i in range(1, 5):
		if mul(i, 1) == last:
			r = i
			q = 4
			for j in range(2, n + 1):
				r = solveNK(s % 10 ** j, j, r, q)
				q = q * 5
			return r

def solve(x):
	return solveK(solveS(x))
N = int(input())
ans = ''
for i in range(0, N):
	x = int(input())
	gg = solve(x)
	ans += '%d\n' % solve(x)
print(ans)


import sys

def phi(p, i):
	if i == 0:
		return 1
	return p ** i - p ** (i - 1)

def pwr(x, p, mod):
	if p == 0:
		return 1
	if p % 2 == 1:
		return x * pwr(x * x % mod, p // 2, mod) % mod
	else:
		return pwr(x * x % mod, p // 2, mod)
n = int(input())
m = 6
for _ in range(0, n):
	x = input()
	k = len(x) + m
	ten = 10 ** k
	two = 2 ** k
	five = 5 ** k
	x = int(x)
	x *= 10 ** m
	x += ((two - x) % two + two) % two
	if x % 5 == 0:
		x += two
	x /= two
	ans = 0
	for i in range(1, k + 1):
		y = x % 5 ** i
		for j in range(0, 5):
			d = ans + j * phi(5, i - 1)
			if pwr(2, d, 5 ** i) == y:
				ans = d
				break
	print(ans + k)


def dlog(x, n):
	bigMod = 5 ** n
	ans = [None, 0, 1, 3, 2][x % 5]
	val = 2 ** ans % bigMod
	(mod, phi) = (5, 4)
	phiVal = 2 ** phi % bigMod
	for i in range(2, n + 1):
		nextMod = mod * 5
		while val % nextMod != x % nextMod:
			val = val * phiVal % bigMod
			ans += phi
		phi *= 5
		phiVal = phiVal * phiVal % bigMod * phiVal % bigMod * phiVal % bigMod * phiVal % bigMod
		mod = nextMod
	return ans

def main():
	inp = input()
	n = len(inp)
	a = int(inp)
	for m in range(n + 1):
		l = a * 10 ** m
		(x, mod) = (l, 2 ** (n + m))
		if x % mod != 0:
			x += mod - x % mod
		if x % 5 == 0:
			x += mod
		if x < l + 10 ** m:
			x = x // mod
			mod = 5 ** (n + m)
			print(n + m + dlog(x % mod, n + m))
			return

def __starting_point():
	cnt = int(input())
	for i in range(cnt):
		main()
__starting_point()


MOD = 10 ** 18

def pow2(n):
	if n == 0:
		return 1
	if n % 2:
		return 2 * pow2(n - 1) % MOD
	c = pow2(n // 2)
	return c * c % MOD
n = int(input())
start2 = pow2(1000)
p2 = [pow2(4 * 5 ** x) for x in range(50)]
c2 = [10 ** x for x in range(50)]
c3 = [4 * 5 ** x for x in range(50)]
for tt in range(n):
	q = int(input())
	f = q * 10 ** 7
	f = f // 2 ** 18
	f = f + 1
	while f % 5 == 0:
		f = f + 1
	f = f * 2 ** 18
	ans = 1000
	s2 = start2
	for i in range(1, 19):
		while pow2(ans) % c2[i] != f % c2[i]:
			if i == 1:
				ans = ans + 1
				s2 = s2 * 2 % MOD
			elif i > 1:
				ans = ans + c3[i - 2]
				s2 = s2 * p2[i - 2] % MOD
	print(ans)


def lift(n, a):
	x = 0
	while pow(2, x, 5) != a % 5:
		x += 1
	for i in range(2, n + 1):
		(mod, phi, step) = (pow(5, i), 4 * pow(5, i - 1), 4 * pow(5, i - 2))
		while pow(2, x, mod) != a % mod:
			x += step
			if x >= phi:
				x -= phi
	return x

def solve(a):
	n = len(str(a))
	m = 0
	while 10 ** m / 2 ** (n + m) * 4 / 5 < n + m + 1:
		m += 1
	(pw2, pw5) = (2 ** (n + m), 5 ** (n + m))
	b = a * 10 ** m % pw2
	if b != 0:
		b = pw2 - b
	while b < 10 ** m:
		if b % 5 != 0:
			k = lift(n + m, (a * 10 ** m + b) % pw5)
			if k >= n + m:
				return k
		b += pw2
for _ in range(int(input())):
	a = int(input())
	k = solve(a)
	assert str(a) in str(pow(2, k, 10 ** 100))
	print(k)


import time
start = time.time()
mod = 5
G = 4

def ModPow(exp):
	if exp == 0:
		return 1
	if exp % 2 == 1:
		return 2 * ModPow(exp - 1) % mod
	A = ModPow(exp // 2)
	return A * A % mod
t = int(input())
while t > 0:
	t = t - 1
	x = int(input())
	mod = 5
	G = 4
	a = 10 ** 12 * x
	k = 2 ** 23 - a
	k %= 2 ** 23
	k += 2 ** 23
	k %= 2 ** 23
	X = a + k
	if X % 5 == 0:
		X += 2 ** 23
	power = int(0)
	while ModPow(power) % 5 != X % 5:
		power = power + 1
	turn = 2
	mod *= 5
	while turn <= 23:
		while ModPow(power) % mod != X % mod:
			power += G
		turn = turn + 1
		mod = mod * 5
		G = G * 5
	print(power)
end = time.time()