Charlie and Johnny play a game. For every integer $\mbox{X}$ Charlie gives, Johnny has to find the smallest positive integer $\mathbf{Y}$ such that $X\times Y$ ($\mbox{X}$ multiplied by $\mathbf{Y}$) contains only 4s and 0s and starts with one or more 4s followed by zero or more 0s. For example, 404 is an invalid number but 4400, 440, and 444 are valid numbers. 

If $\boldsymbol{a}$ is the number of 4s and $\boldsymbol{b}$ is the number of 0s, can you print the value of $(2\times a)+b$?  

Input Format  

The first line of input contains a single integer $\mathbf{T}$, the number of test cases.  

$\mathbf{T}$ lines follow, each line containing the integer $\mbox{X}$ as stated above.

Output Format  

For every $\mbox{X}$, print the output $(2\times a)+b$ in a newline as stated in the problem statement.  

Constraints  

$1\leq T\leq100$ 

$1\leq X\leq10^{10}$  

Sample Input  

3
4
5
80

Sample Output  

2
3
4

Explanation  

For the 1^{st} test case, the smallest such multiple of $4}$ is 4 itself. Hence the value of $\boldsymbol{a}$ will be $\mbox{1}$ and and the value of $\boldsymbol{b}$ will be $\mbox{0}$, and the answer is $(2\times a)+b=2$.  

For the 2^{nd} test case, $Y=8$ and 40 is the minimum such multiple of $5$. Hence the values of $\boldsymbol{a}$, $\boldsymbol{b}$ and $(2\times a)+b$ will be $\mbox{1}$, $\mbox{1}$ and $3$ respectively.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
import fractions
maxN = 100000
isPrime = [True] * (maxN + 1)
isPrime[0] = isPrime[1] = False
prime = []
for i in range(2, maxN + 1):
	if isPrime[i]:
		for j in range(i + i, maxN + 1, i):
			isPrime[j] = False
		prime.append(i)

def check(x, l):
	(rem, p, e) = (0, 4, 10)
	while l:
		if l & 1 == 1:
			rem = (rem * e + p) % x
		p = (p * e + p) % x
		e = e * e % x
		l >>= 1
	return rem == 0

def solve(x):
	y = x
	(c2, c5) = (0, 0)
	while x % 2 == 0:
		c2 += 1
		x //= 2
	while x % 5 == 0:
		c5 += 1
		x //= 5
	zero = max(max(c2 - 2, 0), c5)
	(p, c) = ([], [])
	for i in range(len(prime)):
		if prime[i] * prime[i] > x or x <= 1:
			break
		if x % prime[i] == 0:
			cnt = 0
			p.append(prime[i])
			while x % prime[i] == 0:
				x //= prime[i]
				cnt += 1
			c.append(cnt)
	if x > 1:
		p.append(x)
		c.append(1)
	m = [0] * len(p)
	for i in range(0, len(p)):
		if p[i] == 3:
			m[i] = 3
			continue
		p1 = int(p[i] - 1)
		p2 = int(p1 ** 0.5)
		m[i] = p1
		flag = False
		for j in range(2, p2 + 1):
			if p1 % j == 0:
				flag = check(p[i], j)
				if flag:
					m[i] = j
					break
		if not flag:
			for j in range(p2 + 1, 1, -1):
				if p1 % j == 0:
					flag = check(p[i], p1 // j)
					if flag:
						m[i] = p1 // j
						break
	for i in range(len(p)):
		m[i] *= int(p[i]) ** int(c[i] - 1)
	four = 1
	if len(m) > 0:
		four = m[0]
	for i in range(1, len(p)):
		four = four * m[i] / fractions.gcd(four, m[i])
	return int(four) * 2 + zero
T = int(input())
for _ in range(T):
	x = int(input())
	print(solve(x))


import collections
import math
import operator as op
import sys
from functools import reduce

def get_prime_factors(n):
	factors = collections.defaultdict(int)
	k = 2
	while k * k <= n:
		while n % k == 0:
			factors[k] += 1
			n //= k
		k += 1
	if n > 1:
		factors[n] = 1
	return factors

def get_divisors(n):
	divisors = [1, n]
	for d in range(1, int(math.sqrt(n)) + 1):
		if n % d == 0:
			divisors.extend([d, n // d])
	return sorted(divisors)

def totient(n):
	return reduce(op.mul, [(k - 1) * k ** (v - 1) for (k, v) in get_prime_factors(n).items()], 1)
T = int(sys.stdin.readline())
for _ in range(T):
	X = int(sys.stdin.readline())
	if X == 1 or X == 2 or X == 4:
		print(2)
	else:
		(twos, fives) = (0, 0)
		while X % 2 == 0:
			X //= 2
			twos += 1
		while X % 5 == 0:
			X //= 5
			fives += 1
		b = max(twos - 2, fives)
		a = min((d for d in get_divisors(totient(9 * X)) if pow(10, d, 9 * X) == 1))
		print(2 * a + b)


import fractions
maxN = 100000
isPrime = [True] * (maxN + 1)
isPrime[0] = isPrime[1] = False
prime = []
for i in range(2, maxN + 1):
	if isPrime[i]:
		for j in range(i + i, maxN + 1, i):
			isPrime[j] = False
		prime.append(i)

def check(x, l):
	(rem, p, e) = (0, 4, 10)
	while l:
		if l & 1 == 1:
			rem = (rem * e + p) % x
		p = (p * e + p) % x
		e = e * e % x
		l >>= 1
	return rem == 0

def solve(x):
	y = x
	(c2, c5) = (0, 0)
	while x % 2 == 0:
		c2 += 1
		x //= 2
	while x % 5 == 0:
		c5 += 1
		x //= 5
	zero = max(max(c2 - 2, 0), c5)
	(p, c) = ([], [])
	for i in range(len(prime)):
		if prime[i] * prime[i] > x or x <= 1:
			break
		if x % prime[i] == 0:
			cnt = 0
			p.append(prime[i])
			while x % prime[i] == 0:
				x //= prime[i]
				cnt += 1
			c.append(cnt)
	if x > 1:
		p.append(x)
		c.append(1)
	m = [0] * len(p)
	for i in range(0, len(p)):
		if p[i] == 3:
			m[i] = 3
			continue
		p1 = int(p[i] - 1)
		p2 = int(p1 ** 0.5)
		m[i] = p1
		flag = False
		for j in range(2, p2 + 1):
			if p1 % j == 0:
				flag = check(p[i], j)
				if flag:
					m[i] = j
					break
		if not flag:
			for j in range(p2 + 1, 1, -1):
				if p1 % j == 0:
					flag = check(p[i], p1 // j)
					if flag:
						m[i] = p1 // j
						break
	for i in range(len(p)):
		m[i] *= int(p[i]) ** int(c[i] - 1)
	four = 1
	if len(m) > 0:
		four = m[0]
	for i in range(1, len(p)):
		four = four * m[i] / fractions.gcd(four, m[i])
	return int(four) * 2 + zero
T = int(input())
for _ in range(T):
	x = int(input())
	print(solve(x))


from fractions import gcd

def primes(limit):
	if limit >= 2:
		yield 2
	import array
	from math import sqrt
	isprime = array.array('B', b'\x01' * ((limit - 1) // 2))
	sieveend = sqrt(limit)
	for i in range(len(isprime)):
		if isprime[i] == 1:
			p = i * 2 + 3
			yield p
			if i <= sieveend:
				for j in range(p * p - 3 >> 1, len(isprime), p):
					isprime[j] = 0
ps = list(primes(10 ** 6))

def reduce(func, list, start):
	for elem in list:
		start = func(start, elem)
	return start

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

def isPrime(p):
	return p > 1 and all((f == p for (f, e) in factored(p)))

def factored(a):
	for p in ps:
		j = 0
		while a % p == 0:
			a //= p
			j += 1
		if j > 0:
			yield (p, j)
		if a < p * p:
			break
	if a > 1:
		yield (a, 1)

def multOrdr1(a, x):
	(p, e) = x
	m = p ** e
	t = (p - 1) * p ** (e - 1)
	qs = [1]
	for f in factored(t):
		qs = [q * f[0] ** j for j in range(1 + f[1]) for q in qs]
	qs.sort()
	for q in qs:
		if pow(a, q, m) == 1:
			break
	return q

def multOrder(a, m):
	assert gcd(a, m) == 1
	mofs = (multOrdr1(a, r) for r in factored(m))
	return reduce(lcm, mofs, 1)

def max_p(n, p):
	res = 0
	while n % p == 0:
		n //= p
		res += 1
	return res

def g(x):
	x //= gcd(x, 4)
	twos = max_p(x, 2)
	fives = max_p(x, 5)
	b = max(twos, fives)
	x = x // 2 ** twos // 5 ** fives
	count = 1 % x
	a = multOrder(10, 9 * x)
	return 2 * a + b
for _ in range(int(input())):
	x = int(input())
	print(g(x))


from math import gcd

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

def divisors(n):
	v = []
	d = 1
	while d * d <= n:
		if n % d == 0:
			v.append(d)
			ndivd = n // d
			if ndivd > d:
				v.append(ndivd)
		d += 1
	v.sort()
	return v

def calc(x):
	g = gcd(x, 4)
	x //= g
	e2 = 0
	while x % 2 == 0:
		x //= 2
		e2 += 1
	e5 = 0
	while x % 5 == 0:
		x //= 5
		e5 += 1
	b = max(e2, e5)
	x *= 9
	phix = phi(x)
	vd = divisors(phix)
	for d in vd:
		if pow(10, d, x) == 1:
			a = d
			break
	return 2 * a + b
T = int(input())
for _ in range(T):
	X = int(input())
	print(calc(X))


import sys
from time import time
from random import randrange

def primes_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 pfs_gen(n, prms):
	for p in prms:
		if n < p:
			break
		cnt = 0
		while n % p == 0:
			cnt += 1
			n //= p
		if cnt:
			yield (p, cnt)
	if n > 1:
		yield (n, 1)

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

def totient(n, prms):
	t = 1
	for (p, c) in pfs_gen(n, prms):
		t *= (p - 1) * pow(p, c - 1)
	return t

def repunit_prime(p):
	t = p - 1
	rt = int(pow(t, 0.5))
	ff = []
	for f in range(1, rt + 1):
		if t % f == 0:
			ff.append(t // f)
			if pow(10, f, p) == 1:
				return f
	for f in ff[::-1]:
		if pow(10, f, p) == 1:
			return f
	return None

def get_repunit(n, prms):
	(g, total) = (None, 1)
	for (p, c) in pfs_gen(n, prms):
		k = repunit_prime(p)
		if g is None:
			g = k
		else:
			g = gcd(g, k)
		total *= k * pow(p, c - 1)
	return total // g

def get_repunit_for_divisor(f):
	p = 9 * f
	k = 0
	while True:
		k += 1
		if pow(10, k, p) == 1:
			return k

def get_repunit_for_prime(p):
	rt = int(pow(p - 1, 0.5))
	for f in range(1, rt + 1):
		if pow(10, f, p) == 1:
			return f
	return p - 1

def solve_bf(x, prms):
	(cnt2, cnt5) = (0, 0)
	(g, total) = (None, 1)
	for (p, c) in pfs_gen(x, prms):
		if p == 2:
			cnt2 = c
		elif p == 5:
			cnt5 = c
		else:
			k = repunit_prime(p) * pow(p, c - 1)
			if p == 3:
				k *= 3
			if g is None:
				g = k
			else:
				g = gcd(g, k)
			total *= k
	print('x=%d total=%d g=%s cnt2=%d cnt5=%d' % (x, total, g, cnt2, cnt5), file=sys.stderr)
	if g is not None and g != total:
		total //= g
	rval = total * 2 + max(cnt2 - 2, cnt5)
	return rval

def solve(x, prms):

	def repunit(n, prms):
		t = totient(n, prms)
		rt = int(pow(t, 0.5))
		ff = []
		for f in range(1, rt + 1):
			if t % f == 0:
				ff.append(t // f)
				if pow(10, f, n) == 1:
					return f
		for f in ff[::-1]:
			if pow(10, f, n) == 1:
				return f
		return 1
	(cnt2, cnt5) = (0, 0)
	while x % 2 == 0:
		cnt2 += 1
		x //= 2
	while x % 5 == 0:
		cnt5 += 1
		x //= 5
	r = repunit(x * 9, prms)
	print('x=%d r=%s cnt2=%d cnt5=%d' % (x, r, cnt2, cnt5), file=sys.stderr)
	f = 1
	return 2 * r * f + max(cnt2 - 2, cnt5)
tm = time()
N = pow(10, 5)
prms = tuple(primes_gen(N))
print('primes generated: %s' % (len(prms),), file=sys.stderr)
t = int(input())
for _ in range(t):
	x = int(input())
	print(solve(x, prms))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


import collections
import math
import operator as op
import sys
from functools import reduce

def get_prime_factors(n):
	factors = collections.defaultdict(int)
	k = 2
	while k * k <= n:
		while n % k == 0:
			factors[k] += 1
			n //= k
		k += 1
	if n > 1:
		factors[n] = 1
	return factors

def get_divisors(n):
	divisors = [1, n]
	for d in range(1, int(math.sqrt(n)) + 1):
		if n % d == 0:
			divisors.extend([d, n // d])
	return sorted(divisors)

def totient(n):
	return reduce(op.mul, [(k - 1) * k ** (v - 1) for (k, v) in get_prime_factors(n).items()], 1)
T = int(sys.stdin.readline())
for _ in range(T):
	X = int(sys.stdin.readline())
	if X == 1 or X == 2 or X == 4:
		print(2)
	else:
		(twos, fives) = (0, 0)
		while X % 2 == 0:
			X //= 2
			twos += 1
		while X % 5 == 0:
			X //= 5
			fives += 1
		b = max(twos - 2, fives)
		a = min((d for d in get_divisors(totient(9 * X)) if pow(10, d, 9 * X) == 1))
		print(2 * a + b)


def get_phi(n):
	ret = 1
	i = 2
	while i * i <= n:
		if n % i == 0:
			ret *= i - 1
			n //= i
			while n % i == 0:
				ret *= i
				n //= i
		i += 1
	if n > 1:
		ret *= n - 1
	return ret

def check_all_divisors(n, x):
	ret = n
	i = 1
	while i * i <= n:
		if n % i == 0:
			if pow(10, i, x) == 1:
				return i
			if pow(10, n // i, x) == 1:
				ret = n // i
		i += 1
	return ret
T = int(input())
for cn in range(1, T + 1):
	x = int(input())
	(two, five) = (0, 0)
	while x % 2 == 0:
		two += 1
		x //= 2
	while x % 5 == 0:
		x //= 5
		five += 1
	phi_x = get_phi(9 * x)
	a = check_all_divisors(get_phi(9 * x), 9 * x)
	b = max(two - 2, five)
	print(a + a + b)