Manasa was sulking her way through a boring class when suddenly her teacher singled her out and asked her a question. He gave her a number n and Manasa has to come up with the smallest number m which contains atleast n number of zeros at the end of m!. Help Manasa come out of the sticky situation. 

Input Format 

The first line contains an integer T i.e. the number of Test cases. 

Next T lines will contain an integer n.  

Output Format 

Print smallest such number m. 

Constraints 

1 ≤ T ≤ 100 

1 ≤ n ≤ 10^{16}  

Sample Input  

3
1
2
3

Sample Output  

5
10
15

Explanation

As 4! = 24 and 5! = 120, so minimum value of m will be 5.
As 9! = 362880 and 10! = 3628800, so minimum value of m will be 10.
As 14! = 87178291200 and 15! = 1307674368000, so minimum value of m will be 15.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
from sys import stdin
from math import log, ceil
T = int(stdin.readline())

def invf(n):
	if n == 0:
		return 0
	return sum((n // 5 ** i for i in range(1, int(log(n, 5)) + 1)))

def bsearch(inv, y):
	lb = 1
	ub = y * 5
	while ub - lb > 1:
		mid = (ub + lb) // 2
		if inv(mid) >= y:
			ub = mid
		elif inv(mid) < y:
			lb = mid
	if inv(lb) == y:
		return lb
	else:
		return ub
f = lambda x: bsearch(invf, x)
for _ in range(T):
	print(f(int(stdin.readline())))


bases = [1 for i in range(10000)]
for i in range(1, 10000):
	bases[i] = 5 * bases[i - 1] + 1
t = int(input())
for i in range(t):
	inputx = int(input())
	output = []
	for base in reversed(bases):
		output.insert(0, inputx // base)
		inputx = inputx % base
	x = 0
	prev = 1
	for o in output:
		x += 5 * prev * o
		prev *= 5
	print(x)


def count_fives(n):
	count = 0
	while n > 0:
		n = int(n / 5)
		count += n
	return count
T = int(input())
for t in range(T):
	N = int(input())
	lo = 1
	hi = 5 ** 24
	while hi - lo > 5:
		mid = int((hi + lo) / 10) * 5
		cf = count_fives(mid)
		if cf == N:
			hi = mid
			lo = hi - 5
			break
		elif cf < N:
			lo = mid
		else:
			hi = mid
	print(hi)


import re
from functools import reduce

def f(n):
	if n == 0:
		return 1
	return reduce(lambda a, b: a * b, range(1, n + 1))

def ndiv(n, d):
	a = 0
	while n % d == 0 and n > 0:
		n /= d
		a += 1
	return a

def z(n):
	s = 0
	d = 5
	while d <= n:
		s += n // d
		d *= 5
	return s

def bisect(g):
	upper = 10 ** 20
	lower = 1
	while upper - lower > 1:
		mid = (upper + lower) // 2
		zmid = z(mid)
		if zmid < g:
			lower = mid
		else:
			upper = mid
	if z(lower) >= g:
		return lower
	else:
		return upper

def brute(n):
	s = str(f(n))
	m = re.findall('0+$', s)
	return len(m[0]) if len(m) > 0 else 0
for _ in range(int(input())):
	k = int(input())
	print(bisect(k))


def f(x):
	ans = x
	while x > 0:
		x //= 5
		ans += x
	return ans
for _ in range(int(input())):
	n = int(input())
	a = 1
	b = n
	while a + 1 < b:
		m = (a + b) // 2
		if f(m) >= n:
			b = m
		else:
			a = m
	print(5 * b)


def read_ints():
	return map(int, input().strip().split())

def v(num, p):
	con = True
	res = 0
	ppow = p
	while con:
		partial = num // ppow
		ppow *= p
		res += partial
		con = partial > 0
	return res

def bs(a, b, foo):
	while a + 1 < b:
		p = (a + b) // 2
		if foo(p):
			a = p
		else:
			b = p
	return a

def test(n):
	return bs(1, 5 * n + 1, lambda x: v(x, 5) < n) + 1
(T,) = read_ints()
for x in range(T):
	(n,) = read_ints()
	print(test(n))


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


def pcount(p, n):
	if n == 0:
		return 0
	return n // p + pcount(p, n // p)
t = int(input())
for _ in range(t):
	n = int(input())
	(l, r) = (0, 5 * n)
	while l + 1 < r:
		m = (l + r) // 2
		if pcount(5, m) < n:
			l = m
		else:
			r = m
	print(r)


def test(n, N):
	while n > 0:
		n //= 5
		N -= n
	return N <= 0

def solve(N):
	(n, d) = (1, 5)
	while d < N:
		n += d
		d *= 5
	m = N * d // n
	m -= m % 5
	while not test(m, N):
		m += 5
	return m
T = int(input())
for _ in range(T):
	print(solve(int(input())))


def magic(m):
	m1 = m * 5
	m2 = (m - 1) * 5
	count_zeros1 = count_zeros_factorial(m1)
	count_zeros2 = count_zeros_factorial(m2)
	if count_zeros2 < n <= count_zeros1:
		return 0
	elif count_zeros1 < n:
		return 1
	else:
		return -1

def count_zeros_factorial(m):
	count_zeros = 0
	while m >= 5:
		m //= 5
		count_zeros += m
	return count_zeros

def binSearch(start, fin, func):
	mid = (fin + start) // 2
	func_mid = func(mid)
	if func_mid == 0:
		return mid * 5
	elif func_mid == 1:
		return binSearch(mid + 1, fin, func)
	else:
		return binSearch(start, mid, func)
for t in range(int(input())):
	n = int(input())
	print(binSearch(0, n + 1, magic))


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


import math
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(input())
for _ in range(T):
	n = int(input())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


def zeroes(n):
	s = 0
	while n >= 5:
		n //= 5
		s += n
	return s

def smaller_number(x):
	a = 0
	b = x * 50 + 1
	while b - a > 1:
		m = (a + b) // 2
		if zeroes(m) < x:
			a = m
		else:
			b = m
	return b
tests = int(input())
while tests > 0:
	tests -= 1
	x = int(input())
	print(smaller_number(x))


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


import math
LARGE = 10 ** 16
LARGEST_MUL = int(math.log(LARGE) // math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in range(1, LARGEST_MUL + 1)]
t = int(input())
while t:
	t -= 1
	n = int(input())
	result = 0
	for (i, M) in reversed(multiplicities):
		if M <= n:
			q = n // M
			n -= M * q
			result += 5 ** i * q
	print(result)


def how_many_zeros(N):
	Z = 0
	P = 1
	while True:
		P *= 5
		D = N // P
		if D == 0:
			break
		Z += D
	return Z

def upper_limit(N):
	ls = 10
	while how_many_zeros(ls) < N:
		ls *= 10
	return ls

def solve(N, li, ls):
	if li > ls:
		return li
	m = li + (ls - li) // 2
	hmz = how_many_zeros(m)
	if hmz >= N:
		return solve(N, li, m - 1)
	else:
		return solve(N, m + 1, ls)
T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	print(solve(N, 1, upper_limit(N)))


def count_zeroes(n):
	(res, temp) = (0, 5)
	while n // temp > 0:
		res += n // temp
		temp *= 5
	return res
t = int(input())
for i in range(t):
	n = int(input())
	(left, right, flag, mid) = (1, 5 * n + 1, 0, 0)
	while flag == 0 and left <= right:
		mid = (left + right) // 2
		temp = count_zeroes(mid)
		temp2 = count_zeroes(mid - 1)
		if temp < n:
			left = mid + 1
			continue
		if temp >= n and temp2 < n:
			flag = 1
		else:
			right = mid - 1
	print(mid)


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


M = 250000000000000000

def zeros(n):
	temp = 5
	res = 0
	while temp <= n:
		res += n // temp
		temp *= 5
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	b = 0
	e = M
	while b + 1 < e:
		s = (b + e) // 2
		temp = zeros(s)
		if temp < n:
			b = s + 1
		else:
			e = s + 1
		if b + 2 == e:
			break
	for x in range(b, e + 1):
		if zeros(x) >= n:
			print(x)
			break


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


from math import log

def ntz(p):
	l = int(log(p, 5)) + 1
	return sum((p // 5 ** i for i in range(1, l)))
t = int(input())
for _ in range(t):
	z = int(input())
	p = z * 5 - 5 * z // 25 * 5
	while ntz(p) < z:
		p += 5
	print(p)


def fac(n):
	if n < 5:
		return n * 5
	k = 0
	pOf5 = 1
	newN = 4 * n + 1
	while pOf5 <= newN:
		k += 1
		pOf5 *= 5
	k -= 1
	pOf5 //= 5
	zeros = (pOf5 - 1) // 4
	m = n // zeros
	zeros = m * zeros
	return m * pOf5 + fac(n - zeros)
for _ in range(int(input())):
	n = int(input())
	print(fac(n))


def fact_pow(n, k):
	res = 0
	while n > 0:
		n //= k
		res += n
	return res
for t in range(int(input())):
	n = int(input())
	lo = 0
	hi = n * 5 + 1
	while lo < hi:
		mid = lo + (hi - lo) // 2
		if fact_pow(mid, 5) < n:
			lo = mid + 1
		else:
			hi = mid
	print(hi)


from math import log, ceil

def num_zeros(num):
	return sum((num // 5 ** i for i in range(ceil(log(num, 5)) + 1)))

def inv_num_zeros(num):
	return num - sum((num // 6 ** i for i in range(1, ceil(log(num, 6)) + 1)))
for _ in range(int(input())):
	n = int(input())
	answer = inv_num_zeros(n)
	while num_zeros(answer) > n:
		answer -= 1
	while num_zeros(answer) < n:
		answer += 1
	print(5 * answer)


def trail_zero(n):
	r = 0
	d = 5
	while n >= 5:
		r += n // d
		n //= d
	return r
for i in range(int(input())):
	n = int(input())
	lo = 5
	upper = n * 5
	while lo < upper:
		mid = (lo + upper) // 2
		if trail_zero(mid) < n:
			lo = mid + 1
		else:
			upper = mid
	lo -= lo % 5
	print(lo)


arr = [[5, 1]]
for i in range(1, 30):
	arr.append([arr[-1][0] * 5, arr[-1][1] * 5 + 1])

def f(n):
	a = [0, 29]
	while a[1] - a[0] != 1:
		b = (a[0] + a[1]) // 2
		if n >= arr[b][1]:
			a[0] = b
		else:
			a[1] = b
	return a[0]
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	m = 0
	while n > 0:
		c = f(n)
		m += arr[c][0] * (n // arr[c][1])
		n %= arr[c][1]
	print(m)


def Is_Possible(num, x):
	n = int(5)
	cnt = int(0)
	while 1:
		y = num // n
		if y == 0:
			break
		cnt += y
		n = n * 5
	if cnt >= x:
		return 1
	else:
		return 0

def solve():
	x = int(input())
	lo = 5
	hi = 1000000000000000000
	while lo < hi:
		mid = (lo + hi) // 2
		flag = Is_Possible(mid, x)
		if flag == 1:
			hi = mid
		else:
			lo = mid + 1
	print(lo)

def main():
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


import math

def otherTerms(j1):
	a1 = j1
	a1 = a1 // 5
	s1 = a1
	while a1 > 0:
		a1 = a1 // 5
		s1 = s1 + a1
	return s1
nTst = int(input())
for ii in range(nTst):
	nn = int(input())
	j0 = nn
	n_approx = nn + 1
	cont = True
	while cont:
		others = otherTerms(j0)
		n_approx = j0 + others
		j1 = nn - others
		if j0 == j1:
			cont = False
		if n_approx < nn:
			cont = False
		else:
			j0 = j1
	if n_approx < nn:
		while j1 - j0 > 1:
			jtmp = math.ceil((j0 + j1) // 2)
			n_approx = jtmp + otherTerms(jtmp)
			if n_approx >= nn:
				j1 = jtmp
			else:
				j0 = jtmp
	print(j1 * 5)


from functools import lru_cache

@lru_cache(maxsize=None)
def zeros_gen(a):
	result = 0
	five_p = 5
	while five_p <= a:
		result += a // five_p
		five_p *= 5
	return result
t = int(input())
for _ in range(t):
	n = int(input())
	(a, b, c) = (0, 5 * 10 ** 16, 0)
	while a < b:
		c = (a + b) // 2
		if zeros_gen(c) < n:
			a = c + 1
		else:
			b = c
	print(a)


import math

def fives(n):
	power = 5
	number = 0
	while n >= power:
		number += n // power
		power = power * 5
	return number

def fun(x):
	if x < 5:
		return 0
	return x // 5 + fun(x // 5)
count = int(input())
for i in range(count):
	n = int(input())
	low = 0
	high = 5 * n
	while high - low > 1:
		mid = high + low >> 1
		if fives(mid) < n:
			low = mid
		else:
			high = mid
	print(low + 5 - low % 5)


import sys
from math import floor, log
cases = int(input().strip())
for i in range(cases):
	num = int(input().strip())
	result = 0
	while num > 0:
		n = 0
		while 5 ** n - 1 <= 4 * num:
			n += 1
		n -= 1
		b = int((5 ** n - 1) / 4)
		k = num // b
		result += k * 5 ** n
		num -= k * b
	print(int(result))


def calc(n):
	curpow = 5
	acc = 0
	while n // curpow > 0:
		acc += n // curpow
		curpow *= 5
	return acc
for _ in range(int(input())):
	n = int(input())
	m = 4 * n
	m_lo = m // 5 * 5
	while calc(m_lo) < n:
		m_lo += 5
	print(m_lo)


from math import floor, ceil

def fact(n):
	up = 1000000000000000000
	low = n
	while up > low:
		piv = up + low
		piv = piv >> 1
		piv = piv - piv % 5
		if piv < low:
			piv = low + 1
		if piv > up:
			piv = up - 1
		t = getZero(piv)
		if t == n:
			return redc(piv)
		if t < n:
			low = piv + 1
		if t > n:
			up = piv - 1
	if t < n:
		return redc(piv + 5)
	return redc(piv)

def redc(n):
	r = n % 5
	return n - r

def getZero(n):
	count = 0
	i = 5
	while n // i >= 1:
		count += floor(n // i)
		i = i * 5
	return count
args = int(input())
tests = []
buff = ''
for i in range(0, args):
	tests.append(int(input()))
for case in tests:
	buff += str(fact(case)) + '\n'
print(buff)


def fun(x):
	if x < 5:
		return 0
	return x // 5 + fun(x // 5)
for i in range(int(input())):
	m = int(input())
	begin = 0
	end = m * 5
	temp = 0
	while end - begin > 1:
		mid = begin + end >> 1
		if fun(mid) < m:
			begin = mid
		else:
			end = mid
	print(end)


import math
import fileinput
l = list()

def f(n):
	if n < 5:
		return 0
	return int(n / 5) + f(n / 5)

def kf(x):
	return int(math.log(x) / math.log(5))
for n in range(50):
	l.append((int(f(5 ** n)), kf(5 ** n)))

def g(k, r):
	taljare = 0
	for n in range(1, k + 1):
		taljare = taljare + 5 ** (k - n)
	if taljare == 0:
		return 0
	return r * 5 ** k / taljare
s = 0
for line in fileinput.input():
	u = 0
	x = 0
	s = s + 1
	ins = int(line)
	h = 0
	n = 0
	while ins > l[n][0]:
		n = n + 1
	if ins < l[n][0]:
		n = n - 1
	if s != 1:
		svar = int(g(l[n][1], ins))
		if f(svar) < ins:
			while f(svar + h) < ins:
				h = h + 1
		if f(svar + h) > ins:
			while f(svar + h) > ins:
				h = h - 1
		if int(str(svar + h)[-1:]) != 0 or int(str(svar + h)[-1:]) != 5:
			while int(str(svar + h + u)[-1:]) != 0 and int(str(svar + h + u)[-1:]) != 5:
				u = u + 1
		print(svar + h + u)


def fives(n):
	if n < 5:
		return 0
	if n % 5:
		return fives(n - n % 5)
	return n // 5 + fives(n // 5)
t = int(input())
for i in range(t):
	n = int(input())
	lo = 0
	hi = n * 5
	while hi - lo > 1:
		pivot = (lo + hi) // 2
		if fives(pivot) < n:
			lo = pivot
		else:
			hi = pivot
	print(hi)


import sys

def solve(n):

	def get_zeros(f):
		sm = 0
		while f:
			sm += f // 5
			f //= 5
		return sm
	(f1, f2) = (0, 5 * n)
	while f2 - f1 > 1:
		f = (f1 + f2) // 2
		z = get_zeros(f)
		if z > n:
			(f1, f2) = (f1, f)
		else:
			(f1, f2) = (f, f2)
	(z1, z2) = (get_zeros(f1), get_zeros(f2))
	if z1 == n:
		return f1 - f1 % 5
	return f2 - f2 % 5
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n))


def fives(n):
	r = 0
	while n >= 5:
		n //= 5
		r += n
	return r

def manasa(k):
	if k < 5:
		return 5 * k
	(a, b) = (20, 5 * k)
	(fa, fb) = (4, fives(b))
	while fb > k and b - a > 5:
		c = (a + b) // 10 * 5
		fc = fives(c)
		if fc == k:
			return c
		if fc > k:
			(b, fb) = (c, fc)
		else:
			(a, fa) = (c, fc)
	return b
t = int(input())
for _ in range(t):
	k = int(input())
	print(manasa(k))


def zeroes(m):
	if m < 5:
		return 0
	return m // 5 + zeroes(m // 5)
t = int(input())
for _ in range(t):
	n = int(input())
	s = 0
	e = 5 * n
	f = e
	while s <= e:
		m = s + (e - s + 1) // 2
		k = zeroes(m)
		if k >= n:
			f = m
			e = m - 1
		else:
			s = m + 1
	print(f - f % 5)


from math import log
for _ in range(int(input())):
	n = int(input())
	maxi = int(log(10 ** 16) / log(5)) + 1
	t = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, maxi + 1))]
	r = 0
	for (i, j) in t:
		if j <= n:
			c = n // j
			n -= c * j
			r += c * 5 ** i
	print(r)


def getHighestPowerOf5(n):
	a0 = 0
	a1 = 1
	m0 = 1
	m1 = 5
	while a1 <= n:
		a0 = a1
		m0 = m1
		a1 = a1 * 5 + 1
		m1 *= 5
	m1 = m0
	n -= a0
	while a0 > 0 and a0 <= n:
		n -= a0
		m0 += m1
	return (m0, n)

def getM(n):
	r = n
	m = 0
	while r >= 6:
		(m0, r) = getHighestPowerOf5(r)
		m += m0
	m += r * 5
	return m

def doIt():
	Ts = input()
	T = int(Ts)
	for i in range(T):
		ns = input()
		n = int(ns)
		print(getM(n))
doIt()


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


def numOfZeros(m):
	ret = 0
	while m != 0:
		m //= 5
		ret += m
	return ret

def solve(x):
	(lo, hi) = (0, x * 5)
	while lo < hi:
		mid = (lo + hi) // 2
		if numOfZeros(mid) < x:
			lo = mid + 1
		else:
			hi = mid
	return lo
for _ in range(int(input())):
	print(solve(int(input())))


def zeros(m):
	result = 0
	while m:
		m //= 5
		result += m
	return result

def main():
	for i in range(int(input())):
		n = int(input())
		m = 4 * n
		while zeros(m) < n:
			m += 1
		print(m)
main()


def zeros(n):
	if n == 0:
		return 0
	return n // 5 + zeros(n // 5)
for _ in range(int(input())):
	n = int(input())
	left = 0
	right = 1
	while zeros(right) <= n:
		right *= 2
	while left + 1 < right:
		med = (left + right) // 2
		if zeros(med) < n:
			left = med
		else:
			right = med
	print(right)


def count_zeroes(m):
	s = 0
	while m >= 5:
		m = m // 5
		s += m
	return s
T = int(input())
for t in range(T):
	n = int(input())
	(N, M) = (4 * n, 5 * n)
	m = 0
	while M > N + 1:
		m = (M + N) // 2
		if count_zeroes(m) < n:
			N = m
		else:
			M = m
	print(M)


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


def factorial(n):
	count = 0
	power = 0
	while n >= 5 ** (power + 1):
		power += 1
	for i in range(1, power + 1):
		count += n // 5 ** i
	return count

def main(n, lower, upper):
	if upper == lower:
		return lower
	if upper - lower == 1:
		if factorial(lower) >= n:
			return lower
		return upper
	if factorial((upper + lower) // 2) >= n:
		return main(n, lower, (upper + lower) // 2)
	return main(n, (upper + lower) // 2 + 1, upper)
for i in range(1, int(input()) + 1):
	n = int(input())
	print(main(n, 0, 5 * n))


FIVE_POWERS = [5 ** i for i in range(1, 26)]

def factorial_trailing_zeros(n):
	return sum((n // factor for factor in FIVE_POWERS))

def smallest_m_with_n_trailing_zeros(n):
	m = 4 * n
	m -= m % 5
	while factorial_trailing_zeros(m) >= n:
		m -= 5
	while factorial_trailing_zeros(m) < n:
		m += 5
	assert factorial_trailing_zeros(m) >= n and factorial_trailing_zeros(m - 5) < n
	return m
for _ in range(int(input().strip())):
	print(smallest_m_with_n_trailing_zeros(int(input().strip())))


a = 1
p = [1]
q = [0]
while a < 10 ** 18:
	q += [a + q[-1]]
	a *= 5
	p += [a]
p = p[::-1]
q = q[::-1]
for t in range(int(input())):
	n = int(input())
	res = 0
	for i in range(len(p) - 1):
		d = divmod(n, q[i])
		n = d[1]
		res += d[0] * p[i]
	print(res)


t = int(input())
a = [pow(5, x) for x in range(30)]
for x in range(t):
	n = int(input())
	done = False
	(b, e) = (1, int(1e+30))
	m = (b + e) // 2
	while e > b + 1:
		zm = sum([m // a[r] for r in range(1, 30)])
		if zm >= n:
			e = m
		else:
			b = m
		m = (b + e) // 2
	print(e)


def zer(n):
	k = n // 5
	s = k
	while k > 0:
		k = k // 5
		s += k
	return s
T = int(input())
for i in range(T):
	n = int(input())
	j = 4 * n // 5 * 5
	while zer(j) < n:
		j += 5
	print(j)


def fun(x):
	if x < 5:
		return 0
	return x // 5 + fun(x // 5)
for i in range(int(input())):
	m = int(input())
	begin = 0
	end = m * 5
	temp = 0
	while end - begin > 1:
		mid = begin + end >> 1
		if fun(mid) < m:
			begin = mid
		else:
			end = mid
	print(end)


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(binarySearch(n, L, R) * 5)

def binarySearch(n, l, r):
	while l < r:
		m = median(l, r)
		v = countZeros(m * 5)
		if v == n:
			return m
		elif v < n:
			l = m + 1
		else:
			r = m
	return l

def countZeros(n):
	div = 5
	val = int(n / div)
	ans = 0
	while val > 0:
		ans += val
		div *= 5
		val = int(n / div)
	return ans

def median(l, r):
	temp = l % 2 + r % 2
	if temp == 0:
		m = l / 2 + r / 2
	elif temp == 1:
		if l % 2 == 1:
			m = (l - 1) / 2 + r / 2
		else:
			m = l / 2 + (r - 1) / 2
	else:
		m = (l + 1) / 2 + (r - 1) / 2
	return int(m)
L = 1
R = 50000000000000000
main()


for _ in range(int(input())):
	n = int(input())
	m = 0
	while n > 0:
		power = 1
		s = 1
		while n >= s:
			s += 5 ** power
			power += 1
		n -= s - 5 ** (power - 1)
		m += 5 ** (power - 1)
	print(m)


def zeros(n):
	f = 5
	z = 0
	while f <= n:
		z = z + n // f
		f = f * 5
	return z

def func(n):
	lo = 1
	hi = 10 ** 25
	ans = -1
	while lo <= hi:
		mid = (lo + hi) // 2
		z = zeros(mid)
		if z >= n:
			ans = mid
			hi = mid - 1
		if z < n:
			lo = mid + 1
	return ans
t = int(input())
while t > 0:
	n = int(input())
	res = func(n)
	print(res)
	t = t - 1


T = int(input().strip())
for _ in range(T):
	n = int(input().strip())
	(mini, maxi) = (1, 10 ** 16)
	while mini <= maxi:
		cur = (mini + maxi) // 2
		cur2 = cur
		s = 0
		while cur2 > 0:
			(s, cur2) = (s + cur2, cur2 // 5)
		if s <= n:
			mini = cur + 1
		else:
			maxi = cur - 1
	while True:
		(cur, s) = (maxi, 0)
		while cur > 0:
			(s, cur) = (s + cur, cur // 5)
		if s < n:
			break
		maxi -= 1
	while True:
		(cur, s) = (maxi, 0)
		while cur > 0:
			(s, cur) = (s + cur, cur // 5)
		if s >= n:
			break
		maxi += 1
	print(maxi * 5)


import math
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(input())
a = []
for _ in range(T):
	n = int(input())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	a.append(m)
for i in range(len(a)):
	print(a[i])


import math
line = input()
ctests = int(line)
for itest in range(ctests):
	line = input()
	n = int(line)
	nZerosAtPowers = [1]
	i = 0
	while True:
		k = 5 * nZerosAtPowers[i] + 1
		if k <= n:
			nZerosAtPowers.append(k)
			i += 1
		if k >= n:
			break
	m = 0
	while n > 0:
		last = nZerosAtPowers[i]
		if last <= n:
			n -= last
			m += 5 ** (i + 1)
		else:
			i -= 1
	print(m)


def f(m, n):
	(d, a) = (0, 5)
	while m // a > 0:
		d += m // a
		a *= 5
	if d >= n:
		return False
	else:
		return True
for _ in range(int(input())):
	n = int(input())
	m = n * 4
	while f(m, n):
		m += 1
	print(m)


def zeros(num):
	if num < 5:
		return 0
	return num // 5 + zeros(num // 5)
T = int(input())
for _ in range(T):
	n = int(input())
	start = 4 * n
	end = 5 * n
	while end - start > 1:
		mid = (start + end) // 2
		if zeros(mid) < n:
			start = mid
		else:
			end = mid
	print(end)


def valuation5(N):
	s = 0
	while N:
		N //= 5
		s += N
	return s
T = int(input().strip())
for _ in range(T):
	n = int(input().strip())
	candidate = 1 + 4 * n
	while valuation5(candidate) < n:
		candidate += 1
	print(candidate)


import math
from bisect import bisect_left
nums = [1, 6, 31, 156, 781, 3906, 19531, 97656, 488281, 2441406, 12207031, 61035156, 305175781, 1525878906, 7629394531, 38146972656, 190734863281, 953674316406, 4768371582031, 23841857910156, 119209289550781, 596046447753906, 2980232238769531, 14901161193847656]

def firstPowBelow(n):
	for i in range(0, 23):
		if nums[i] <= n and nums[i + 1] > n:
			return i + 1
	return 23

def valAtPow(pow):
	res = 1
	spow = 1
	while spow < pow:
		res = res + 5 ** spow
		spow = spow + 1
	return res

def ans(i):
	topPow = firstPowBelow(i)
	i = i - valAtPow(topPow)
	d = 5 ** topPow
	while i > 0:
		topPow = firstPowBelow(i)
		d = d + 5 ** topPow
		i = i - valAtPow(topPow)
	return d
for _ in range(int(input())):
	i = int(input())
	print(ans(i))


def n_fives(x):
	f = 5
	n_fives = 0
	while f <= x:
		n_fives += x // f
		f *= 5
	return n_fives

def brute_n_fives(x):
	total = 0
	for i in range(1, x + 1):
		n_fives = 0
		while not i % 5 and n_fives < 50:
			n_fives += 1
			i //= 5
		total += n_fives
	return total

def test_n_fives():
	for i in range(1000):
		x = n_fives(i)
		y = brute_n_fives(i)
		assert x == y, 'i={} x={} y={}'.format(i, x, y)
	print('test_n_fives passed')

def binary_search(x):
	left = x // 10
	right = x * 10
	while right - left > 1:
		middle = (right + left) // 2
		if n_fives(middle) >= x:
			right = middle
		else:
			left = middle
	return right

def brute_search(x):
	i = 1
	while n_fives(i) < x:
		i += 1
	return i

def test_search():
	for i in range(1, 100):
		x = binary_search(i)
		y = brute_search(i)
		assert x == y, 'i={} x={} y={}'.format(i, x, y)
	print('test_search passed')
t = int(input())
for _ in range(t):
	n = int(input())
	print(binary_search(n))


def nzer(n):
	x = 1
	d = 5
	c = 0
	while x > 0:
		x = n // d
		c += x
		d *= 5
	return c
for _ in range(int(input())):
	n = int(input())
	if n <= 5:
		print(5 * n)
	else:
		x = n * 4
		if n % 5 != 0:
			x = x + 5 - x % 5
		y = n * 5
		for i in range(x, y, 5):
			if nzer(i) >= n:
				print(i)
				break


def solve(Z):
	N = 0
	while True:
		n = 5
		z = 1
		while z < Z:
			n *= 5
			z *= 5
			z += 1
		if z == Z:
			return N + n
		z -= 1
		z //= 5
		Z -= z
		N += n // 5
T = int(input())
for t0 in range(T):
	print(solve(int(input())))


import math

def zeros(n):
	x = 0
	while n > 0:
		a = n // 5
		x = x + a
		n = n // 5
	return x
for i in range(int(input())):
	n = int(input())
	k = 4 * n + 1
	while True:
		a = zeros(k)
		if a >= n:
			print(k)
			break
		k = k + 1


import math
Max_rank = 25

def multiple(n):
	k = 5
	res = 0
	while k <= n:
		res += n // k
		k *= 5
	return res

def fact(n):
	k = 5
	res = 0
	while n % k == 0:
		res += 1
		k *= 5
	return res

def least_pow(n):
	res = 0
	k = 5
	while k <= n:
		k *= 5
		res += 1
	return res
Power = [1]
Power_effect = [0]
k = 5
for i in range(Max_rank):
	Power.append(k)
	Power_effect.append(1 + 5 * Power_effect[i])
	k *= 5
max_multiple = multiple(Power[Max_rank])
nLines = int(input())
for i in range(nLines):
	n = int(input())
	rank = Max_rank
	current = Power[rank]
	current_multiple = max_multiple
	factors = rank
	while rank > 0:
		rank -= 1
		if current_multiple - factors + rank - n < 1:
			continue
		else:
			alpha = (current_multiple - factors + rank - n) // Power_effect[rank]
			if alpha != 0:
				current -= alpha * Power[rank]
				current_multiple = multiple(current)
				factors = fact(current)
			continue
	print(current)


def fact0(m):
	cpt = 0
	p5 = 5
	while p5 <= m:
		cpt += m // p5
		p5 *= 5
	return cpt

def main():
	T = int(input())
	for _ in range(T):
		n = int(input())
		(a, b) = (0, 1 << 56)
		while a < b:
			m = (a + b) // 2
			if fact0(m) < n:
				a = m + 1
			else:
				b = m
		print(a)
main()


for _ in range(int(input())):
	x = int(input())
	(l, r) = (0, 10 ** 17)
	while l + 1 < r:
		mid = (l + r) // 2
		cnt = 0
		base = 5
		while base <= mid:
			cnt += mid // base
			base *= 5
		if cnt >= x:
			r = mid
		else:
			l = mid
	print(r)


def cal(n):
	if n < 5:
		return 0
	else:
		return n // 5 + cal(n // 5)
for i in range(int(input())):
	c = int(input())
	low = 5
	high = c * 5
	while high - low > 1:
		mid = (low + high) // 2
		if cal(mid) < c:
			low = mid
		else:
			high = mid
	print(high)


powers = []
power = 5
while power <= 5 * 10 ** 16:
	powers.append(power)
	power *= 5

def num_zeros(n):
	ret = 0
	for power in powers:
		if power <= n:
			ret += n // power
		else:
			break
	return ret
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	head = n
	tail = 5 * n + 1
	while head < tail - 1:
		mid = (head + tail) // 2
		tmp = num_zeros(mid)
		if tmp < n:
			head = mid
		else:
			tail = mid
	print(tail)


import math, sys
MAX_N = 10 ** 16
MAX_MULT = int(math.log(MAX_N) / math.log(5)) + 1
multiplicities = [(i, (5 ** i - 1) // 4) for i in reversed(range(1, MAX_MULT + 1))]
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	m = 0
	for (k, p) in multiplicities:
		if p <= n:
			i = n // p
			n -= i * p
			m += i * 5 ** k
	print(m)


def cnt_zeros(n):
	c = 0
	while n > 0:
		c += n // 5
		n = n // 5
	return c
T = int(input())
for _ in range(T):
	n = int(input())
	s = 1
	z = 1
	while cnt_zeros(z) < n:
		z *= 2
	while z - s > 2:
		sr = (z + s) // 2
		if cnt_zeros(sr) >= n:
			z = sr
		else:
			s = sr
	for k in range(s, z + 1):
		if cnt_zeros(k) >= n:
			print(k)
			break


def f(n):
	if n == 1:
		return 5

	def check(p, n):
		(t, c, f) = (p, 0, 5)
		while f <= t:
			c += t // f
			f *= 5
		return c >= n
	(l, h) = (0, 5 * n)
	while l < h:
		m = l + h >> 1
		if check(m, n):
			h = m
		else:
			l = m + 1
	return l
print('\n'.join(map(str, map(f, [int(input()) for x in range(int(input()))]))))


def f(n):
	res = 0
	while n:
		res += n // 5
		n //= 5
	return res
for _ in range(int(input())):
	n = int(input())
	high = 5 * n
	low = 0
	while high > low:
		mid = (low + high) // 2
		if f(mid) >= n:
			high = mid
		else:
			low = mid + 1
	else:
		print(high)


import math

def find_p_power(n):
	if n == 0:
		return 0
	p = 0
	while (pow(5, p) - 1) // 4 <= n:
		p += 1
	return pow(5, p - 1) + find_p_power(n - (pow(5, p - 1) - 1) // 4)
test_cases = int(input())
for i in range(0, test_cases):
	n = int(input())
	print(find_p_power(n))


def fun(x):
	if x < 5:
		return 0
	return x // 5 + fun(x // 5)
for i in range(int(input())):
	m = int(input())
	begin = 0
	end = m * 5
	temp = 0
	while end - begin > 1:
		mid = begin + end >> 1
		if fun(mid) < m:
			begin = mid
		else:
			end = mid
	print(end)


def num_zeros(n):
	cnt = 0
	d = 5
	while d <= n:
		cnt += n // d
		d *= 5
	return cnt

def find_min(n):
	bot = 1
	top = -1
	top = 40000000000000025
	m = max(top // 2, 1)
	last = m
	while True:
		z = num_zeros(m)
		if z >= n and num_zeros(m - 1) < n:
			break
		elif z < n:
			bot = max(bot, m)
			if top < 0:
				m *= 10
			else:
				last = m
				m = 1 + m + (top - m) // 2
		else:
			if top < 0:
				top = m
			else:
				top = min(top, m)
			last = m
			m = bot + (top - bot) // 2
		assert last != m
	return m
for _ in range(int(input())):
	n = int(input())
	print(find_min(n))


def count5(n):
	sum = 0
	product = 1
	while product < n:
		product *= 5
		sum += n // product
	return sum
for _ in range(int(input())):
	n = int(input())
	j = (4 * n + 4) // 5 * 5
	while count5(j) < n:
		j += 5
	print(j)


from math import pow
maxN = int(pow(10, 16))

def comp(n):
	counter = 0
	i = 1
	while counter < n:
		t = i
		while t % 5 == 0:
			counter += 1
			t = int(t / 5)
		i += 1
	return i - 1

def createArray():
	A = [1]
	i = 2
	while A[-1] < maxN:
		A.append(A[-1] * 5 + 1)
		i += 1
	return A

def solve(A, n):
	ret = 0
	i = len(A) - 1
	while i >= 0:
		den = int(n / A[i])
		n %= A[i]
		ret = ret * 5 + den
		i -= 1
	return ret * 5
T = int(input())
A = createArray()
for i in range(T):
	n = int(input())
	ret = solve(A, n)
	print(ret)


import math

def zero(n):
	s = 0
	while n > 0:
		s += n // 5
		n = n // 5
	return s

def binary(s, e, n):
	while s <= e:
		mid = s + (e - s) // 2
		if zero(mid) == n and zero(mid - 1) < n or (zero(mid) > n and zero(mid - 1) < n):
			return mid
		elif zero(mid) >= n:
			e = mid - 1
		else:
			s = mid + 1
	return -1
for a0 in range(int(input())):
	n = int(input())
	i = 1
	while True:
		if n <= zero(i):
			break
		i = i * 2
	print(binary(i // 2, i, n))


def count_zero(n):
	ginti = 0
	i = 5
	while n // i:
		ginti += n // i
		i *= 5
	return ginti
for _ in range(int(input())):
	n = int(input())
	low = 0
	ans = 0
	high = 50 * n
	while low < high:
		mid = (low + high) // 2
		if count_zero(mid) >= n:
			high = mid
			ans = mid
		else:
			low = mid + 1
	print(ans)


import os
import sys

def get_end_0s_in_fact(num):
	Sum = 0
	while num > 0:
		num = num // 5
		Sum = Sum + num
	return Sum

def get_approx_num(n):
	res = 4 * int(pow(5, least_expo_5(n))) // int(pow(5, least_expo_5(n)) - 1) * n
	return res - res % 5

def least_expo_5(n):
	count = 0
	Sum = 0
	while True:
		Sum = Sum + int(pow(5, count))
		if Sum == n:
			return count + 1
		elif Sum > n:
			return count
		else:
			count += 1

def solve(n):
	approx_num = get_approx_num(n)
	while True:
		if get_end_0s_in_fact(approx_num) >= n:
			return approx_num
		else:
			approx_num += 5
t = int(input())
for t_itr in range(t):
	n = int(input())
	result = solve(n)
	print(result)


m = pow(10, 18)
a = 5
b = 1
dic = []
while a <= m:
	dic.append([a, b])
	a = a * 5
	b = b * 5 + 1
dic.sort(reverse=True)
t = int(input())
for te in range(t):
	n = int(input())
	suma = 0
	for i in range(len(dic)):
		a = dic[i][1]
		suma += dic[i][0] * (n // a)
		n = n % a
	print(suma)