Charlie and Johnny play a game. For every integer X Charlie gives, Johnny has to find the smallest positive integer Y, such that X * Y contains only 4's and 0's and starts with one or more 4's followed by zero or more 0's. (i.e.), 404 is an invalid number but 400 is a valid number. 

If a is the number of 4's and b is the number of 0's, can you print the value of 2 * a + b.

Input Format

The first line contains an integer T. T lines follow, each line containing the integer X as stated above.

Output Format

For every X, print the output 2 * a + b in a newline as stated in the problem statement. 

Constraints

1<=T<=10^{3} 

1<=X<=10^{5}

Sample Input #00

3
4
5
80

Sample Output #00

2
3
4

Explanation 

For the 1^{st} test-case, the smallest such multiple of 4 is 4 itself. Hence value of a will be 1 and and value of b will be 0. The required value of 2 * a+b is 2.     

For the 2^{nd} test-case, Y = 8 and 40 is the minimum such multiple of 5. Hence value of a,b and 2 * a+b will be 1, 1 and 3 respectively.

Difficulty: MEDIUM
Tags: Number theory

Starter code:

Solutions:
from fractions import gcd
from collections import Counter
testcases = int(input())

def factorization(n):
	facts = Counter()
	while not n % 2:
		facts.update({2: 1})
		n //= 2
	tryval = 3
	while tryval ** 2 <= n:
		while not n % tryval:
			facts.update({tryval: 1})
			n //= tryval
		tryval += 2
	if n > 1:
		facts.update({n: 1})
	return facts

def totient(n):
	prod = 1
	for (p, exp) in factorization(n).items():
		prod *= (p - 1) * p ** (exp - 1)
	return prod

def multorder(n, m):
	if gcd(n, m) != 1:
		return 0
	order = totient(m)
	fact = factorization(order)
	for p in fact:
		while order % p == 0:
			if pow(n, order // p, m) == 1:
				order //= p
			else:
				break
	return order

def lowest40(baseint):
	count2 = 0
	count5 = 0
	while not baseint % 2:
		baseint //= 2
		count2 += 1
	while not baseint % 5:
		baseint //= 5
		count5 += 1
	return 2 * multorder(10, 9 * baseint) + max(count5, count2 - 2)
for test in range(testcases):
	baseint = int(input())
	results = lowest40(baseint)
	print(results)


from math import log10

def caldigit(p):
	c = int(log10(p)) + 1
	a = int('1' * c) % p
	while a:
		a = (a * 10 + 1) % p
		c += 1
	return c
for _ in range(int(input())):
	n = int(input())
	twos = 0
	while not n & 1:
		n >>= 1
		twos += 1
	fives = 0
	while not n % 5:
		n //= 5
		fives += 1
	print(2 * caldigit(n) + max(fives, twos - 2))


def phi(X):
	f = X
	p = 2
	while p <= X:
		if p * p > X:
			p = X
		if X % p == 0:
			f -= f / p
			while X % p == 0:
				X /= p
		p += 1
	return f

def divisors(X):
	p = 1
	while p * p <= X:
		if X % p == 0:
			yield p
		p += 1
	while p >= 1:
		if X % p == 0:
			yield (X / p)
		p -= 1

def F(X):
	if X % 4 == 0:
		return G(X / 4)
	if X % 2 == 0:
		return G(X / 2)
	return G(X)

def G(X):
	a = b = 0
	while X % 2 == 0:
		X /= 2
		a += 1
	while X % 5 == 0:
		X /= 5
		b += 1
	return (H(X), max(a, b))

def H(X):
	X *= 9
	for d in divisors(phi(X)):
		if pow(10, int(d), int(X)) == 1:
			return d
for cas in range(int(input())):
	X = int(input())
	(a, b) = F(X)
	print(int(a * 2 + b))


def divideOutPower(X, power):
	n = 0
	while True:
		if X % power != 0:
			return (X, n)
		n += 1
		X //= power

def findMultiplier(X):
	n = 0
	ones = 0
	while True:
		ones = (10 * ones + 1) % X
		if ones == 0:
			return n + 1
		n += 1

def findResult(X):
	(X, exp10) = divideOutPower(X, 10)
	(X, exp5) = divideOutPower(X, 5)
	(X, exp2) = divideOutPower(X, 2)
	if exp2 <= 2:
		exp2 = 2
	else:
		exp5 += exp2 - 2
	a = findMultiplier(X)
	b = exp10 + exp5
	return 2 * a + b
line = input()
ctests = int(line)
for itest in range(ctests):
	line = input()
	X = int(line)
	print(findResult(X))


import sys

def get_gcd(a, b):
	r = max(a, b)
	d = min(a, b)
	while True:
		if r % d == 0:
			return d
		old_r = r
		r = d
		d = old_r % d

def can_divide_tens(num):
	num_divided_by_two = 0
	num_divided_by_five = 0
	while num % 10 == 0:
		num_divided_by_two += 1
		num_divided_by_five += 1
		num = num / 10
	while num % 2 == 0:
		num_divided_by_two += 1
		num = num / 2
	while num % 5 == 0:
		num_divided_by_five += 1
		num = num / 5
	is_divisible = num == 1
	return (is_divisible, max(num_divided_by_two, num_divided_by_five), num)
for line in sys.stdin.readlines()[1:]:
	num = int(line)
	b = 0
	a = 1
	left = 1
	num_increase = 0
	num_zeros = 0
	is_divisible_by_tens = False
	num = num / get_gcd(num, 4)
	while num % 10 == 0:
		num = num / 10
		b += 1
	while num % 2 == 0:
		num = num / 2
		b += 1
	while num % 5 == 0:
		num = num / 5
		b += 1
	while True:
		if left < num:
			left = left * 10 + 1
			a += 1
		left = left % num
		if left == 0:
			break
	print(2 * a + b)


t = int(input())
for i in range(0, t):
	twocount = 0
	fivecount = 0
	n = int(input())
	while n % 2 == 0:
		n //= 2
		twocount += 1
	while n % 5 == 0:
		n //= 5
		fivecount += 1
	j = max(twocount - 2, fivecount)
	a = 1
	count = 1
	while a % n != 0:
		a = (a * 10 + 1) % n
		count += 1
	print(count * 2 + j)


t = int(input())
for i in range(t):
	n = int(input())
	(x, y) = (0, 0)
	while n % 2 == 0:
		n = n // 2
		x += 1
	while n % 5 == 0:
		n = n // 5
		y += 1
	b = max(x - 2, y)
	a = 1
	arr = 1
	sum1 = 1
	while not sum1 % n == 0:
		a += 1
		arr = arr * 10 % n
		sum1 = (sum1 + arr) % n
	print(2 * a + b)


t = int(input())
for _t in range(t):
	(n, i_mod, n4, dict) = (int(input()), 0, 0, {})
	while True:
		if i_mod in dict:
			break
		dict[i_mod] = n4
		i_mod = i_mod * 10 + 4
		n4 += 1
		if i_mod >= n:
			i_mod %= n
	print(2 * n4 - dict[i_mod])


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	X = int(sys.stdin.readline())
	(twos, fives) = (0, 0)
	while X % 2 == 0:
		X //= 2
		twos += 1
	while X % 5 == 0:
		X //= 5
		fives += 1
	(a, b) = (1, max(twos - 2, fives))
	n = 1
	while n % X > 0:
		n = (10 * n + 1) % X
		a += 1
	print(2 * a + b)


for _ in range(int(input())):
	x = int(input())
	(cnt2, cnt5) = (0, 0)
	while x % 2 == 0:
		cnt2 += 1
		x //= 2
	while x % 5 == 0:
		cnt5 += 1
		x //= 5
	zcnt = max(cnt2 - 2, cnt5)
	(rem, fcnt) = (1 % x, 1)
	while rem > 0:
		rem *= 10
		rem += 1
		rem %= x
		fcnt += 1
	print(fcnt * 2 + zcnt)


def find_ab(x):
	(e2, e5) = (0, 0)
	while x % 2 == 0:
		x //= 2
		e2 += 1
	while x % 5 == 0:
		x //= 5
		e5 += 1
	b = max(e2 - 2, e5)
	a = 1
	cur = 10 % (9 * x)
	while cur != 1:
		a += 1
		cur = cur * 10 % (9 * x)
	return 2 * a + b
T = int(input())
for t in range(T):
	X = int(input())
	print(find_ab(X))


def g(x):
	seen = {0: 0}
	count = 4 % x
	a = 1
	while count not in seen:
		seen[count] = a
		count = count * 10 + 4
		count %= x
		a += 1
	return 2 * a - seen[count]
for _ in range(int(input())):
	x = int(input())
	print(g(x))


t = int(input())
for i in range(t):
	x = int(input())
	expdos = 0
	while x % 2 == 0:
		x = x // 2
		expdos = expdos + 1
	expcinco = 0
	while x % 5 == 0:
		x = x // 5
		expcinco = expcinco + 1
	b = 0
	if expcinco == 0:
		if expdos > 2:
			b = expdos - 2
	elif expcinco + 2 >= expdos:
		b = expcinco
	else:
		b = expdos - 2
	a = 1
	num = 1
	while num % x != 0:
		a = a + 1
		num = (num * 10 + 1) % x
	print(2 * a + b)


def is_prime(x, L=[]):
	sqrt = int(pow(x, 0.5)) + 1
	PL = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 16, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	if not L:
		if x < 210:
			if x in PL:
				return True
			else:
				return False
		else:
			for p in PL:
				if x % p == 0:
					return False
			for i in range(1, sqrt // 210 + 1):
				for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
					if x % (210 * i + j) == 0:
						return False
		return True
	elif x != 0 and x != 1:
		j = 0
		while j < len(L) and L[j] <= sqrt:
			if x % L[j] == 0:
				return False
			j += 1
	else:
		return False
	return True

def prime_list(n):
	L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	for k in range(1, n // 210):
		for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
			if is_prime(210 * k + j, L):
				L.append(210 * k + j)
	k = n // 210
	for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
		if is_prime(210 * k + j, L) and 210 * k + j <= n:
			L.append(210 * k + j)
	return L

def is_miller_rabin(x, num_tests=3):
	k = x - 1
	e = 0
	while k % 2 == 0:
		e += 1
		k //= 2
	tests = [False for _ in range(0, num_tests)]
	A = [2, 3, 5]
	for j in range(3, num_tests):
		A.append(random.randint(7, x - 1))
	if x < 2047:
		num_tests = 1
	elif x < 1373653:
		num_tests = 2
	elif x < 25326001:
		num_tests = 3
	for i in range(0, num_tests):
		ak = pow_mod(A[i], k, x)
		if ak == 1:
			tests[i] = True
		else:
			for j in range(0, e):
				if ak == x - 1:
					tests[i] = True
				ak = ak * ak % x
	for i in range(0, num_tests):
		if not tests[i]:
			return False
	return True

def factor(n, PL):
	sqrt = int(pow(n, 0.5)) + 1
	factor_list = []
	if not PL:
		PL = prime_list(sqrt)
	i = 0
	while i < len(PL) and n > 1:
		p = PL[i]
		if n % p == 0:
			elet = [p, 0]
			while not n % p:
				n //= p
				elet[1] += 1
			factor_list.append(elet)
		i += 1
	if n != 1:
		if is_miller_rabin(n):
			factor_list.append([n, 1])
	return factor_list
PL = prime_list(100000)
T = int(input())
for _ in range(0, T):
	x = int(input())
	factor_list = factor(x, PL)
	two_position = -1
	if factor_list[0][0] == 2:
		two_position = 0
	five_position = -1
	i = 0
	while i < min(3, len(factor_list)) and factor_list[i][0] != 5:
		i += 1
	if i < min(3, len(factor_list)):
		five_position = i
	if five_position == -1 and two_position == -1:
		b = 0
	elif five_position == -1 and two_position == 0:
		if factor_list[two_position][1] > 2:
			b = factor_list[two_position][1] - 2
		else:
			b = 0
		x //= pow(2, factor_list[two_position][1])
	elif five_position != -1 and two_position == -1:
		b = factor_list[five_position][1]
		x //= pow(5, factor_list[five_position][1])
	elif five_position != -1 and two_position == 0:
		if factor_list[two_position][1] - 2 >= factor_list[five_position][1]:
			b = factor_list[two_position][1] - 2
		else:
			b = factor_list[five_position][1]
		x //= pow(2, factor_list[two_position][1])
		x //= pow(5, factor_list[five_position][1])
	t = 1
	a = 1
	while t % x:
		a += 1
		t *= 10
		t += 1
		t %= x
	print(2 * a + b)


from fractions import gcd

def calc(n):
	g = gcd(4, n)
	n //= g
	e2 = 0
	while n % 2 == 0:
		e2 += 1
		n //= 2
	e5 = 0
	while n % 5 == 0:
		e5 += 1
		n //= 5
	b = max(e2, e5)
	m = 9 * n
	s = 1
	for i in range(1, m + 1):
		s = s * 10 % m
		if s == 1:
			a = i
			break
	return 2 * a + b
T = int(input())
for i in range(T):
	X = int(input())
	print(calc(X))


import sys

def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi
for _ in range(int(input())):
	n = x = int(input())
	n2 = 0
	while x % 2 == 0:
		n2 += 1
		x //= 2
	n5 = 0
	while x % 5 == 0:
		n5 += 1
		x //= 5
	if False:
		a = EulerPhi(x)
	else:
		y = 1
		a = 1
		while y % x != 0:
			y = (y * 10 + 1) % x
			a += 1
	b = n5
	if n2 - n5 > 2:
		b += n2 - n5 - 2
	print(2 * a + b)


import sys
from time import time

def prime_gen(n):
	sieve = [1] * n
	for p in range(2, n):
		if sieve[p]:
			yield p
			for i in range(p + p, n, p):
				sieve[i] = 0

def get_caches(n):
	pcache = []
	tcache = [1] * n
	tcache[0] = tcache[1] = 0
	for p in prime_gen(n):
		pcache.append(p)
		for i in range(p, n, p):
			tcache[i] *= p - 1
		q = p * p
		while q < n:
			for i in range(q, n, q):
				tcache[i] *= p
			q *= p
	return (pcache, tcache)

def get_factor(x, b):
	f = 0
	while x % b == 0:
		x //= b
		f += 1
	return f

def pf_gen(n, pcache):
	for p in pcache:
		if p > n:
			break
		cnt = 0
		while n % p == 0:
			cnt += 1
			n //= p
		if cnt:
			yield (p, cnt)
	if n > 1:
		yield (n, 1)

def solve(x, pcache, tcache):
	print('x=%d' % (x,), file=sys.stderr)
	f2 = get_factor(x, 2)
	f5 = get_factor(x, 5)
	z = x // pow(2, f2) // pow(5, f5)
	print('\tf2=%d f5=%d z=%d' % (f2, f5, z), file=sys.stderr)
	if f2 <= f5:
		f10 = f5
		f2 = 2
	else:
		df2 = f2 - f5
		if df2 < 2:
			f10 = f5
			f2 = 2 - df2
		else:
			f2 -= 2
			f10 = f2
	print('\tf2=%d f10=%d' % (f2, f10), file=sys.stderr)
	f3 = get_factor(z, 3)
	z //= pow(3, f3)
	print('\tf3=%d z=%d' % (f3, z), file=sys.stderr)
	if z == 1:
		c = pow(3, f3)
	else:
		z *= pow(3, f3)
		t = tcache[z]
		print('\tt=%d' % (t,), file=sys.stderr)
		c = None
		r = int(pow(t, 0.5))
		for d in range(1, r + 1):
			if t % d == 0:
				for f in (d, t // d):
					if pow(10, f, z) == 1:
						if c is None or c > f:
							c = f
							print('\t\td=%d c=%d' % (d, c), file=sys.stderr)
		cf3 = get_factor(c, 3)
		if cf3 < f3:
			c *= pow(3, f3 - cf3)
	(a, b) = (c, f10)
	print('\ta=%d b=%d' % (a, b), file=sys.stderr)
	return 2 * a + b

def solve_bf(x, pcache, tcache):
	print('x=%d' % (x,), file=sys.stderr)
	f2 = get_factor(x, 2)
	f5 = get_factor(x, 5)
	z = x // pow(2, f2) // pow(5, f5)
	print('\tf2=%d f5=%d z=%d' % (f2, f5, z), file=sys.stderr)
	if f2 <= f5:
		f10 = f5
		f2 = 2
	else:
		df2 = f2 - f5
		if df2 < 2:
			f10 = f5
			f2 = 2 - df2
		else:
			f2 -= 2
			f10 = f2
	print('\tf2=%d f10=%d' % (f2, f10), file=sys.stderr)
	c = None
	n = int('1' * z)
	for i in range(z, 0, -1):
		if n % z == 0:
			c = i
		n //= 10
	(a, b) = (c, f10)
	print('\ta=%d b=%d' % (a, b), file=sys.stderr)
	if int('4' * a) * pow(10, b) % x != 0:
		raise Exception('x=%d a=%d b=%d' % (x, a, b))
	return 2 * a + b

def test(fr, to, pcache, tcache):
	for x in range(fr, to):
		(u, v) = (solve(x, pcache, tcache), solve_bf(x, pcache, tcache))
		if u != v:
			print('x=%d u=%d v=%d' % (x, u, v), file=sys.stderr)
tm = time()
N = pow(10, 5)
(pcache, tcache) = get_caches(N + 1)
print('caches generated: %s' % (time() - tm,), file=sys.stderr)
print('pcache=%s' % (pcache[:20],), file=sys.stderr)
print('tcache=%s' % (tcache[:20],), file=sys.stderr)
t = int(input())
for _ in range(t):
	x = int(input())
	print(solve(x, pcache, tcache))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


T = int(input())
A = [-1] * 100000
B = [-1] * 100000
for t in range(T):
	X = int(input())
	r = 0
	for i in range(X + 1):
		if B[r] == t:
			print(2 * i - A[r])
			break
		else:
			A[r] = i
			B[r] = t
		r = (r * 10 + 4) % X


t = int(input())
for _ in range(t):
	x = int(input())
	k = x
	count2 = 0
	count5 = 0
	while x % 2 == 0:
		count2 += 1
		x = x // 2
	while x % 5 == 0:
		count5 += 1
		x = x // 5
	y = 0
	count = 1
	while True:
		y = (10 * y + 1) % x
		if y % x == 0:
			break
		count += 1
	b = max(count2 - 2, count5)
	ans = 2 * count + b
	print(ans)


import os
import sys
for _ in range(int(input())):
	n = x = int(input())
	n2 = 0
	while x % 2 == 0:
		n2 += 1
		x //= 2
	n5 = 0
	while x % 5 == 0:
		n5 += 1
		x //= 5
	if False:
		a = EulerPhi(x)
	else:
		y = 1
		a = 1
		while y % x != 0:
			y = (y * 10 + 1) % x
			a += 1
	b = n5
	if n2 - n5 > 2:
		b += n2 - n5 - 2
	print(2 * a + b)


from functools import reduce
f = {3: 3}

def primeFactorize(n):
	PF = {}
	p = 2
	while p * p <= n:
		if n % p:
			p += 1
		else:
			PF[p] = PF.get(p, 0) + 1
			n = n // p
	if n > 1:
		PF[n] = PF.get(n, 0) + 1
	return PF

def myCounter(dTotal, keyOrder):
	dCount = {key: 0 for key in dTotal}
	while True:
		yield dCount
		bit = 0
		dCount[keyOrder[bit]] += 1
		while dCount[keyOrder[bit]] >= dTotal[keyOrder[bit]]:
			dCount[keyOrder[bit]] = 0
			bit += 1
			if bit == len(keyOrder):
				break
			else:
				dCount[keyOrder[bit]] += 1

def retrieveFactors(n):
	PF = primeFactorize(n)
	myKeys = list(PF.keys())
	CCC = myCounter({k: PF[k] + 1 for k in PF}, myKeys)
	c = next(CCC)
	factors = [1]
	while factors[-1] != n:
		nextFactor = next(CCC)
		factors.append(reduce(lambda x, key: x * key ** c[key], c, 1))
	return factors

def f_p(p):
	facs = sorted(retrieveFactors(p - 1), reverse=True)
	testFactor = facs.pop()
	while pow(10, testFactor, p) != 1:
		testFactor = facs.pop()
	return testFactor

def gcd(a, b):
	(a, b) = sorted([a, b])
	while a:
		(a, b) = (b % a, a)
	return b

def LCM(a, b):
	return a * b // gcd(a, b)

def solve(x):
	PF = primeFactorize(x)
	b = max(PF.pop(2, 0) - 2, PF.pop(5, 0))
	a = 1
	while PF:
		(p, exponent) = PF.popitem()
		f[p] = f.get(p, f_p(p))
		a = LCM(a, p ** (exponent - 1) * f[p])
	return (a, b)
t = int(input())
for t_itr in range(t):
	x = int(input())
	(a, b) = solve(x)
	print(2 * a + b)


for _ in range(int(input())):
	n = x = int(input())
	n2 = 0
	while x % 2 == 0:
		n2 += 1
		x //= 2
	n5 = 0
	while x % 5 == 0:
		n5 += 1
		x //= 5
	if False:
		a = EulerPhi(x)
	else:
		y = 1
		a = 1
		while y % x != 0:
			y = (y * 10 + 1) % x
			a += 1
	b = n5
	if n2 - n5 > 2:
		b += n2 - n5 - 2
	print(2 * a + b)


for _ in range(int(input())):
	n = x = int(input())
	n2 = 0
	while x % 2 == 0:
		n2 += 1
		x //= 2
	n5 = 0
	while x % 5 == 0:
		n5 += 1
		x //= 5
	if False:
		a = EulerPhi(x)
	else:
		y = 1
		a = 1
		while y % x != 0:
			y = (y * 10 + 1) % x
			a += 1
	b = n5
	if n2 - n5 > 2:
		b += n2 - n5 - 2
	print(2 * a + b)


def getnum(n):
	cnt_2 = 0
	cnt_5 = 0
	m = n
	while m % 2 == 0:
		m //= 2
		cnt_2 += 1
	while m % 5 == 0:
		m //= 5
		cnt_5 += 1
	pow_10 = max(cnt_2 - 2, cnt_5)
	num1 = 10 ** pow_10 * 4
	num2 = 1
	rem = 1
	while rem % m:
		num2 += 1
		rem = (rem * 10 + 1) % m
	return num1 * (10 ** num2 - 1) // 9

def solve(n):
	num = str(getnum(n))
	a = num.count('4')
	b = num.count('0')
	print(2 * a + b)
for _ in range(int(input())):
	n = int(input())
	solve(n)


def getnum(n):
	cnt_2 = 0
	cnt_5 = 0
	m = n
	while m % 2 == 0:
		m //= 2
		cnt_2 += 1
	while m % 5 == 0:
		m //= 5
		cnt_5 += 1
	pow_10 = max(cnt_2 - 2, cnt_5)
	num1 = 10 ** pow_10 * 4
	num2 = 1
	rem = 1
	while rem % m:
		num2 += 1
		rem = (rem * 10 + 1) % m
	return num1 * (10 ** num2 - 1) // 9

def solve(n):
	num = str(getnum(n))
	a = num.count('4')
	b = num.count('0')
	return 2 * a + b
for _ in range(int(input())):
	x = int(input())
	print(solve(x))


for _ in range(int(input())):
	n = x = int(input())
	n2 = 0
	while x % 2 == 0:
		n2 += 1
		x //= 2
	n5 = 0
	while x % 5 == 0:
		n5 += 1
		x //= 5
	if False:
		a = EulerPhi(x)
	else:
		y = 1
		a = 1
		while y % x != 0:
			y = (y * 10 + 1) % x
			a += 1
	b = n5
	if n2 - n5 > 2:
		b += n2 - n5 - 2
	print(2 * a + b)


for _ in range(int(input())):
	n = x = int(input())
	n2 = 0
	while x % 2 == 0:
		n2 += 1
		x //= 2
	n5 = 0
	while x % 5 == 0:
		n5 += 1
		x //= 5
	if False:
		a = EulerPhi(x)
	else:
		y = 1
		a = 1
		while y % x != 0:
			y = (y * 10 + 1) % x
			a += 1
	b = n5
	if n2 - n5 > 2:
		b += n2 - n5 - 2
	print(2 * a + b)


def getnum(n):
	cnt_2 = 0
	cnt_5 = 0
	m = n
	while m % 2 == 0:
		m //= 2
		cnt_2 += 1
	while m % 5 == 0:
		m //= 5
		cnt_5 += 1
	pow_10 = max(cnt_2 - 2, cnt_5)
	num1 = 10 ** pow_10 * 4
	num2 = 1
	rem = 1
	while rem % m:
		num2 += 1
		rem = (rem * 10 + 1) % m
	return num1 * (10 ** num2 - 1) // 9

def solve(n):
	num = str(getnum(n))
	a = num.count('4')
	b = num.count('0')
	return 2 * a + b
for t_itr in range(int(input().strip())):
	result = solve(int(input().strip()))
	print(result)


for _ in range(int(input())):
	n = x = int(input())
	n2 = 0
	while x % 2 == 0:
		n2 += 1
		x //= 2
	n5 = 0
	while x % 5 == 0:
		n5 += 1
		x //= 5
	if False:
		a = EulerPhi(x)
	else:
		y = 1
		a = 1
		while y % x != 0:
			y = (y * 10 + 1) % x
			a += 1
	b = n5
	if n2 - n5 > 2:
		b += n2 - n5 - 2
	print(2 * a + b)


for _ in range(int(input())):
	n = x = int(input())
	n2 = 0
	while x % 2 == 0:
		n2 += 1
		x //= 2
	n5 = 0
	while x % 5 == 0:
		n5 += 1
		x //= 5
	if False:
		a = EulerPhi(x)
	else:
		y = 1
		a = 1
		while y % x != 0:
			y = (y * 10 + 1) % x
			a += 1
	b = n5
	if n2 - n5 > 2:
		b += n2 - n5 - 2
	print(2 * a + b)


for _ in range(int(input())):
	n = x = int(input())
	n2 = 0
	while x % 2 == 0:
		n2 += 1
		x //= 2
	n5 = 0
	while x % 5 == 0:
		n5 += 1
		x //= 5
	if False:
		a = EulerPhi(x)
	else:
		y = 1
		a = 1
		while y % x != 0:
			y = (y * 10 + 1) % x
			a += 1
	b = n5
	if n2 - n5 > 2:
		b += n2 - n5 - 2
	print(2 * a + b)