Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

The Head Chef is receiving a lot of orders for cooking the best of the problems lately. For this, he organized an hiring event to hire some talented Chefs. He gave the following problem to test the skills of the participating Chefs. Can you solve this problem and be eligible for getting hired by Head Chef.

A non-negative number n is said to be magical if it satisfies the following property. Let S denote the multi-set of numbers corresponding to the non-empty subsequences of the digits of the number n in decimal representation. Please note that the numbers in the set S can have leading zeros. Let us take an element s of the multi-set S, prod(s) denotes the product of all the digits of number s in decimal representation. 
The number n will be called magical if sum of prod(s) for all elements s in S, is even. 

For example, consider a number 246, its all possible non-empty subsequence will be S = {2, 4, 6, 24, 46, 26, 246}. Products of digits of these subsequences will be {prod(2) = 2, prod(4) = 4, prod(6) = 6, prod(24) = 8, prod(46) = 24, prod(26) = 12, prod(246) = 48, i.e. {2, 4, 6, 8, 24, 12, 48}. Sum of all of these is 104, which is even. Hence 246 is a magical number.

Please note that multi-set S can contain repeated elements, e.g. if number is 55, then S = {5, 5, 55}. Products of digits of these subsequences will be {prod(5) = 5, prod(5) = 5, prod(55) = 25}, i.e. {5, 5, 25}. Sum of all of these is 35 which is odd. Hence 55 is not a 
magical number.

Consider a number 204, then S = {2, 0, 4, 20, 04, 24, 204}. Products of digits of these subsequences will be {2, 0, 4, 0, 0, 8, 0}. Sum of all these elements will be 14 which is even. So 204 is a magical number.

The task was to simply find the K^{th} magical number.

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

First line of the input contains an integer T denoting the number of test cases.
Each of the next T lines contains a single integer K.

------ Output ------ 

For each test case, print a single integer corresponding to the K^{th} magical number.

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

1 ≤ T ≤ 10^{5}
1 ≤ K ≤ 10^{12}.

------ Subtasks ------ 

Subtask #1 : (20 points)

1 ≤ T ≤ 100
1 ≤ K ≤ 10^{4}.

Subtask 2 : (80 points) 
Original Constraints

----- Sample Input 1 ------ 
2

2

5
----- Sample Output 1 ------ 
2

8
----- explanation 1 ------ 
Example case 1.
2 is the 2nd magical number, since it satisfies the property of the magical number. The first magical number will be of course 0.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
t = int(input())
for i in range(t):
	k = int(input())
	k -= 1
	arr = []
	while True:
		arr += [str(2 * (k % 5))]
		k = int(k / 5)
		if k == 0:
			break
	arr = reversed(arr)
	print(int(''.join(arr)))


import math
for _ in range(int(input())):
	k = int(input())
	if k == 1:
		print(0)
	else:
		k -= 1
		s = ''
		p = int(math.log(k, 5))
		m = pow(5, p)
		for i in range(p, -1, -1):
			s += str(k // m * 2)
			k %= m
			m //= 5
		print(int(s))


t = int(input())
for _ in range(t):
	n = int(input())
	n = n - 1
	mul = 1
	res = 0
	while n:
		res += 2 * (n % 5) * mul
		n = n // 5
		mul *= 10
	print(res)


def convertToBase5(n):
	ans = []
	while n:
		ans.append(n % 5)
		n = n // 5
	return ans[::-1]
T = int(input())
for i in range(T):
	K = int(input())
	answerList = convertToBase5(K - 1)
	if K == 1:
		print('0')
	else:
		s = ''
		for x in answerList:
			s = s + str(2 * int(x))
		print(s)


for t in range(int(input())):
	k = int(input())
	k -= 1
	res = 0
	i = 1
	while k != 0:
		res += k % 5 * i
		k //= 5
		i *= 10
	print(res * 2)


t = 0
k = 0
t = int(input())
d = 0
num = 0
for i in range(0, t):
	num = 0
	mult = 1
	k = int(input())
	k = k - 1
	if k == 0:
		print(0)
	else:
		while k > 0:
			d = k % 5 * 2
			k = int(k / 5)
			num = d * mult + num
			mult = mult * 10
		print(num)


def func(j):
	if j == 0:
		return 0
	else:
		return j % 5 * 2 + func(j // 5) * 10
t = int(input())
for i in range(0, t):
	k = int(input())
	m = func(k - 1)
	print(m)


from math import log
T = int(input())
for _ in range(T):
	X = int(input()) - 1
	magic = 0
	if X:
		loga = int(log(X, 5))
		if loga:
			for macht in range(loga):
				if X > 0:
					macht = loga - macht
					aantal = X // 5 ** macht
					magic += aantal * 2 * 10 ** int(log(X, 5))
					X -= aantal * 5 ** macht
		magic += 2 * X
		print(magic)
	else:
		print(0)


def snek(k):
	s = ' '
	while k:
		s += str(k % 5)
		k //= 5
	s = s[::-1]
	return s
t = int(input())
for i in range(t):
	k = int(input())
	if k == 0 or k == 1:
		print(0)
		continue
	k -= 1
	a = snek(k)
	print(int(a) * 2)


case = int(input())
for _ in range(case):
	k = int(input()) - 1
	res = 0
	mul = 1
	while k > 0:
		remai = k % 5
		res = res + 2 * remai * mul
		k = k // 5
		mul *= 10
	print(res)


import sys
T = int(sys.stdin.readline().rstrip())

def baseN(num, b, numerals='02468'):
	return num == 0 and numerals[0] or baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b]
for _ in range(0, T):
	K = sys.stdin.readline().rstrip()
	print(baseN(int(K) - 1, 5))


xx = [5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125, 6103515625, 30517578125, 152587890625, 762939453125]
t = int(input())
while t > 0:
	a = int(input())
	b = ''
	flag = True
	for i in range(16, -1, -1):
		c = xx[i]
		if a > c:
			if a % c == 0:
				b += str(a // c * 2 - 2)
				b = b + '8' * (i + 1)
				flag = False
				break
			else:
				b += str(a // c * 2)
				a = a % c
		else:
			b += '0'
	if flag:
		b += str((a - 1) * 2)
	print(int(b))
	t -= 1


T = int(input())
for t in range(T):
	n = int(input()) - 1
	digits = []
	while n > 0:
		digits.append(n % 5)
		n = n // 5
	s = 0
	for dg in reversed(digits):
		s *= 10
		s += dg
	print(2 * s)


from math import log
m = 1

def b(j, n):
	global m
	x = (n - 1 - 5 ** m) // 5 ** j
	return int(x)

def oeis(n):
	if n <= 1:
		return 0
	global m
	m = int(log(n - 1, 5))
	sumi = 0
	for j in range(m):
		sumi += 2 * b(j, n) % 10 * 10 ** j
	x = (2 * b(m, n) % 8 + 2) * 10 ** m + sumi
	return int(x)
T = int(input())
for t in range(T):
	n = int(input())
	print(oeis(n))


def base5(n):
	if n == 0:
		return
	for x in base5(n // 5):
		yield x
	yield (n % 5)

def seq(n):
	return 10 * seq(n // 5) + n % 5 * 2 if n else 0
t = int(input())
while t > 0:
	i = int(input())
	print(seq(i - 1))
	t = t - 1


for t in range(int(input())):
	x = int(input())
	y = x - 1
	a = []
	while y != 0:
		a.append(y % 5)
		y = y // 5
	le = len(a)
	if x == 1:
		print('0')
	else:
		for o in range(le):
			print(2 * a[le - o - 1], end='')
	print()


def numberTobase(n, b):
	if n == 0:
		return ['0']
	digits = []
	while n:
		digits.append(str(int(n % b)))
		n //= b
	return digits[::-1]
for _ in range(int(input())):
	k = int(input())
	print(2 * int(''.join(numberTobase(k - 1, 5))))


def base5(n):
	if n == 0:
		return
	for x in base5(n // 5):
		yield x
	yield (n % 5)

def seq(n):
	return int(''.join((str(2 * x) for x in base5(n))) or '0')
t = int(input())
while t > 0:
	i = int(input())
	print(seq(i - 1))
	t = t - 1


t = int(input())
for i in range(t):
	z = 1
	ans = 0
	n = 0
	s = int(input())
	while s != 0:
		power = 10 ** n
		s = s - z
		x = s % 5
		s = s // 5
		ans = ans + power * x
		n = n + 1
		z = 0
	ans = ans * 2
	print(ans)


from math import log, floor, ceil
digit = [8, 6, 4, 2, 0]
T = int(input().strip())
for each in range(T):
	x = int(input().strip())
	if x == 1:
		print(0)
		continue
	d = ceil(log(x, 5))
	ans = ''
	while d > 0:
		dis = 5 ** d - x
		gap = 5 ** (d - 2) * 5
		c = floor(dis / gap)
		ans += str(digit[c])
		d -= 1
		x = x - gap * (4 - c)
	print(int(ans))


import sys
l = [0, 2, 4, 6, 8]
for _ in range(int(sys.stdin.readline())):
	x = int(sys.stdin.readline()) - 1
	g = ''
	while x:
		g = str(x % 5 << 1) + g
		x //= 5
	if g == '':
		sys.stdout.write('0\n')
	else:
		sys.stdout.write(g + '\n')


def b5(n):
	if n > 0:
		return 10 * b5(n // 5) + n % 5 * 2
	else:
		return 0
t = int(input())
while t > 0:
	n = int(input())
	x = b5(n - 1)
	print(x)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	s = []
	temp = n - 1
	if n == 1:
		print(0)
	else:
		while temp > 0:
			d = temp % 5
			s.append(d)
			temp //= 5
		s = list(map(str, s))
		s = ''.join(s)
		s = s[::-1]
		s = int(s)
		print(s * 2)


t = int(input())
while t > 0:
	n = int(input())
	x = n - 1
	s = ''
	if x == 0:
		print(0)
	else:
		while x:
			mod = x % 5
			x = x // 5
			s = chr(48 + mod + 7 * (mod > 10)) + s
		print(int(s) * 2)
	t = t - 1


def get_number_of_digits(n):
	d = 0
	while int(n) > 0:
		n = n / 5
		d += 1
	return d

def get_digits(K):
	num = 0
	d = get_number_of_digits(K) - 1
	p = 1
	for i in range(d):
		p = p * 5
	while p > 0:
		num = num * 10 + int(K / p) * 2
		K = K % p
		p = int(p / 5)
	return num
T = int(input())
for t in range(T):
	K = int(input())
	print(get_digits(K - 1))


power_count = 18
powers = [0] * 18
powers[0] = 1
for i in range(1, power_count):
	powers[i] = powers[i - 1] * 5
T = int(input())
for _ in range(T):
	K = int(input())
	K -= 1
	ans = ''
	for i in range(power_count - 1, -1, -1):
		dv = K // powers[i]
		if ans != '' or dv != 0:
			ans += str(dv * 2)
		K -= dv * powers[i]
	if ans == '':
		print(0)
	else:
		print(ans)


t = int(input())
while t:
	val = int(input())
	faltu = []
	val = val - 1
	while val > 0:
		faltu.append(val % 5)
		val //= 5
	s = 0
	for i in range(len(faltu)):
		s = s + faltu[i] * 10 ** i
	print(s * 2)
	t -= 1


def base10toN(num, base):
	(converted_string, modstring) = ('', '')
	currentnum = num
	if not 1 < base < 37:
		raise ValueError('base must be between 2 and 36')
	if not num:
		return '0'
	while currentnum:
		mod = currentnum % base
		currentnum = currentnum // base
		converted_string = chr(48 + mod + 7 * (mod > 10)) + converted_string
	return converted_string
t = int(input())
while t:
	x = int(input())
	ans = base10toN(x - 1, 5)
	ans = [int(x) * 2 for x in ans]
	s = ''.join(map(str, ans))
	print(int(s))
	t -= 1


for _ in range(int(input())):
	K = int(input()) - 1
	digits = []
	if K == 0:
		print('0')
	else:
		while K:
			digits.append(2 * int(K % 5))
			K //= 5
		print(''.join([str(m) for m in digits][::-1]))


def soln(num):
	if num == 0 or num == 1:
		return 0
	num -= 1
	res = ''
	while num > 0:
		(div, mod) = divmod(num, 5)
		res += str(mod)
		num = div
	return int(res[::-1]) * 2
for _ in range(int(input())):
	print(soln(int(input())))


for _ in range(int(input())):
	k = int(input())
	k = k - 1
	ans = 0
	mul = 1
	while k:
		ans += k % 5 * 2 * mul
		k = k // 5
		mul = mul * 10
	print(ans)


def decimal_to_quinary(n):
	if n == 0:
		return '0'
	digits = ''
	while n:
		digits += str(n % 5)
		n //= 5
	return digits[::-1]
T = int(input())
for t in range(T):
	K = int(input())
	print(''.join([str(2 * int(d)) for d in decimal_to_quinary(K - 1)]))


def to_base5(n):
	res = []
	while n:
		c = n % 5
		res.append(c)
		n //= 5
	res = res[::-1]
	return int(''.join((str(i) for i in res)))
for _ in range(int(input())):
	n = int(input())
	n = n - 1
	if n == 0:
		print(0)
	else:
		print(2 * to_base5(n))


t = int(input())
for T in range(t):
	n = int(input())
	ans = n * 2 - 2
	p = 5
	m = 10
	while n > p:
		if n % p == 0:
			ans = ans + (n // p - 1) * m
		else:
			ans = ans + n // p * m
		p = p * 5
		m = m * 10
	print(ans)


POWERS_OF_FIVE = [1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125, 6103515625, 30517578125, 152587890625, 762939453125, 3814697265625]
DIGITS = ['0', '2', '4', '6', '8']
T = int(input())

def pretty(number):
	str = ''.join(number).lstrip('0')
	return str if str != '' else '0'

def kth(k):
	number = []
	for base in reversed(POWERS_OF_FIVE):
		number.append(DIGITS[k // base])
		k = k % base
	return number
for i in range(0, T):
	K = int(input())
	print(pretty(kth(K - 1)))


case = int(input())
valid = ['0', '2', '4', '6', '8']

def base5(n):
	result = 0
	i = 0
	while n > 0:
		result += n % 5 * 10 ** i
		i += 1
		n = n // 5
	return result
while case != 0:
	n = int(input())
	n = str(base5(n - 1))
	for digit in n:
		print(valid[int(digit)], end='')
	print('\n', end='')
	case -= 1


def magic(k):
	if k == 0:
		return 0
	ans = 0
	expo = 1
	while k > 0:
		ans += k % 5 * expo
		expo *= 10
		k //= 5
	return 2 * ans
T = int(input())
for i in range(T):
	k = int(input())
	print(magic(k - 1))


def tobase5(x):
	if x == 0:
		return '0'
	a = ''
	while x > 0:
		a += str(2 * (x % 5))
		x //= 5
	return a[::-1]
for i in range(int(input())):
	print(tobase5(int(input()) - 1))


for _ in range(int(input())):
	k = int(input())
	if k == 1:
		print(0)
		continue
	k -= 1
	ans = ''
	while k != 0:
		ans += str(k % 5)
		k = k // 5
	ans = int(ans[::-1])
	print(ans * 2)


t = int(input().strip())

def bass(n):
	s = ''
	while n != 0:
		tt = n % 5
		s += str(tt)
		n = int(n // 5)
	if s == '':
		s = '0'
	return s[::-1]
for i in range(t):
	k = int(input().strip())
	k -= 1
	ans = 2 * int(bass(k))
	print(ans)


def main():
	testCases = int(input())
	results = []
	for i in range(testCases):
		n = int(input())
		results.append(find(n))
	for i in results:
		print(i)

def find(n):
	factor = 2
	answer = 0
	divisor = 1
	while n - 1 >= divisor:
		answer += factor * (int((n - 1) / divisor) % 5)
		divisor *= 5
		factor *= 10
	return answer
main()


t = int(input())
while t:
	t -= 1
	k = int(input())
	k -= 1
	power = 20
	sum = 0
	while power != -1:
		pfl = 5 ** power
		if pfl <= k:
			temp = k // pfl
			temp = temp * 2
			k = k % pfl
			sum += 10 ** power * temp
		power -= 1
	print(sum)


from math import log

def power(k):
	if log(k, 5) == int(log(k, 5)):
		return int(log(k, 5)) - 1
	else:
		return int(log(k, 5))
l = [0, 2, 4, 6, 8, 20, 22, 24, 26, 28, 40, 42, 44, 46, 48, 60, 62, 64, 66, 68, 80, 82, 84, 86, 88]
for t in range(int(input())):
	k = int(input())
	n = power(k)
	a = 5 ** n
	ans = 0
	val = 1
	while k > 24:
		if k % a == 0:
			k = k - 1
			val = 0
		ans += l[k // a] * 10 ** n
		k = k % a
		n -= 1
		a = 5 ** n
	ans += l[k - val]
	print(ans)


t = int(input())
while t:
	t -= 1
	k = int(input())
	k -= 1
	j = 18
	div = 0
	ans = 0
	while j >= 0:
		div = 5 ** j
		if k // div != 0:
			ans += k // div * 10 ** j
			k = k % div
		j -= 1
	print(ans * 2)


import sys

def getk(x):
	if x == 0:
		return 0
	return getk(x // 5) * 10 + x % 5 * 2
f = sys.stdin
n = int(f.readline())
for i in range(n):
	print(getk(int(f.readline()) - 1))


t = int(input())
a = [0, 2, 4, 6, 8]
for i in range(0, t):
	n = int(input()) - 1
	if n == 0:
		print('0')
		continue
	x = []
	while n:
		r = n % 5
		x.append(a[r])
		n //= 5
	for j in range(len(x) - 1, -1, -1):
		print(x[j], end='')
	print()


OddDigitList = ['1', '3', '5', '7', '9']

def GetMultiSetNoRecursion(num):
	lst = []
	multiset = []
	for x in str(num):
		lst.append(x)
	T = list(lst)
	T2 = list(lst)
	multiset.append(lst[0])
	nextDig = 1
	while len(T2) > 1:
		while len(lst) > 1:
			for x in range(1, len(lst)):
				multiset.append(lst[0] + lst[x])
			print(multiset)
			input()
			lst[0] = lst[0] + lst[1]
			lst.remove(lst[1])
			if len(lst) == 1:
				T.remove(T[1])
				lst = list(T)
				if len(lst) == 1:
					break
				else:
					lst[0] = lst[0] + lst[1]
					lst.remove(lst[1])
		T2.remove(T2[0])
		multiset.append(T2[0])
		T = list(T2)
		lst = list(T2)
	return multiset

def GetProductofDigit(N):
	c = 1
	for x in N:
		if x == '0':
			return 0
		c = c * int(x)
	return c

def GetProductSet(multiset):
	productSet = []
	for x in multiset:
		y = GetProductofDigit(x)
		productSet.append(y)
	return productSet

def GetMultiSetNoRecursionStringMethod(num):
	numList = []
	for x in str(num):
		numList.append(x)
	Charlist = list(numList)
	Fullmultiset = []
	LastCharacterPosition = []
	for x in range(0, len(numList)):
		multiset = []
		multiset.append(numList[x])
		LastCharacterPosition.append(x)
		lengthMultiset = len(multiset)
		indexCheckStart = 0
		for y in multiset:
			for pos in range(LastCharacterPosition[multiset.index(y, indexCheckStart)] + 1, len(Charlist)):
				multiset.append(y + Charlist[pos])
				LastCharacterPosition.append(pos)
			indexCheckStart += 1
		Fullmultiset = Fullmultiset + multiset
		LastCharacterPosition = []
	return Fullmultiset

def MagicNumberCheckMathematicalMethod(num):
	numList = []
	for x in str(num):
		if x in OddDigitList:
			return False
	return True

def IsMagicNumberTrue(num):
	multiset = GetMultiSetNoRecursionStringMethod(num)
	productSet = []
	for x in multiset:
		y = GetProductofDigit(x)
		productSet.append(y)
	Sum = 0
	for x in productSet:
		Sum = Sum + x
	if Sum % 2 == 0:
		return True
	else:
		return False

def FindNthMagicalNumber(num):
	num = num - 1
	quotient = 1
	base5list = []
	while num != 0:
		remainder = num % 5
		base5list.append(remainder)
		num = int(num / 5)
	base5Num = 0
	for x in reversed(base5list):
		base5Num = base5Num * 10 + x
	return base5Num * 2

def main2():
	n = int(input())
	print(GetMultiSetNoRecursionStringMethod(n))
	print('Number of Elements in set: ' + str(len(GetMultiSetNoRecursionStringMethod(n))))
	print('Product Set:' + str(GetProductSet(GetMultiSetNoRecursionStringMethod(n))))
	print(IsMagicNumberTrue(n))

def main():
	T = int(input())
	inp = []
	result = []
	for xx in range(0, T):
		inp.append(int(input()))
	largestInput = 0
	for xx in inp:
		if largestInput < xx:
			largestInput = xx
	InputSet = set(inp)
	magicNumberCount = 0
	N = 0
	while magicNumberCount != largestInput:
		if IsMagicNumberTrue(N):
			magicNumberCount += 1
			if magicNumberCount in InputSet:
				result.append(N)
		N = N + 1
	for x in result:
		print(x)

def main3():
	T = int(input())
	inp = []
	for xx in range(0, T):
		Num = int(input())
		inp.append(Num)
	magicNumberCount = 0
	N = -1
	greatest = 0
	for x in inp:
		if x > greatest:
			greatest = x
	result = [None] * greatest
	while magicNumberCount != greatest:
		N = N + 1
		if MagicNumberCheckMathematicalMethod(N):
			magicNumberCount += 1
			if magicNumberCount in inp:
				result[inp.index(magicNumberCount)] = N
	for x in result:
		if x == None:
			continue
		else:
			print(x)

def main4():
	T = int(input())
	result = []
	for x in range(0, T):
		N = int(input())
		result.append(FindNthMagicalNumber(N))
	for x in result:
		print(x)
main4()


def seq(n):
	return 10 * seq(n // 5) + n % 5 * 2 if n else 0
t = int(input())
while t:
	q = int(input())
	print(seq(q - 1))
	t -= 1


import sys
import math
t = int(input())
arr = [8, 0, 2, 4, 6]
while t > 0:
	t -= 1
	k = int(input())
	result = str(arr[k % 5])
	power = 1
	if k % 5 == 0:
		k -= 1
	while power <= 20:
		num = 5 ** power
		if num > k:
			break
		add = int(k / num) % 5
		result = str(arr[(add + 1) % 5]) + result
		power += 1
	print(result)


def MagicalNum(k):
	if 1 <= k <= 5:
		return 2 * (k - 1)
	elif k == 0:
		return 0
	elif k % 5 == 0:
		v1 = k // 5
		return 10 * MagicalNum(v1) + 8
	else:
		v1 = k // 5
		v2 = k % 5
		return 10 * MagicalNum(v1 + 1) + MagicalNum(v2)
T = int(input())
for _ in range(T):
	k = int(input())
	print(MagicalNum(k))


import math
P5 = [1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125, 6103515625, 30517578125, 152587890625, 762939453125, 3814697265625]
t = int(input())
for _t in range(t):
	k = int(input())
	if k == 1:
		print(0)
		continue
	(l, d, lim) = (k - 1, [], math.ceil(math.log(k) / math.log(5)))
	for i in range(lim):
		d.append(l // P5[i] % 5)
	for x in d[::-1]:
		print(2 * x, end='')
	print()


for _ in range(int(input())):
	n = int(input())
	n -= 1
	a = []
	while n > 0:
		a.append(2 * (n % 5))
		n //= 5
	n = len(a)
	if n == 0:
		print('0')
		continue
	for i in range(n):
		print(a[n - 1 - i], end='')
	print()


T = int(input())
for t in range(T):
	K = int(input()) - 1
	b = 2
	ans = 0
	while K:
		ans += K % 5 * b
		b *= 10
		K //= 5
	print(ans)


def base5(k):
	s = ''
	while k:
		s += str(k % 5)
		k //= 5
	s = s[::-1]
	return s
for _ in range(int(input())):
	k = int(input())
	if k == 0 or k == 1:
		print(0)
		continue
	k = k - 1
	ans = base5(k)
	print(int(ans) * 2)


cases = int(input())
for _ in range(cases):
	n = int(input())
	n -= 1
	if n == 0:
		print(0)
	else:
		digits = []
		while n:
			digits.append(str(int(n % 5)))
			n //= 5
		print(int(''.join(digits[::-1])) * 2)


def kthmagical(k):
	if k == 1:
		return 0
	k -= 1
	i = 0
	if k >= cs[0]:
		for i in range(len(cs)):
			if cs[i] > k:
				k -= cs[i - 1]
				break
	ld = i
	ans = []
	while i >= 0:
		if i == 0 and ld > 0:
			ans.append(fdigits[k % 4])
		elif i == 0 and ld == 0:
			return even[k % 5]
		else:
			ans.append(even[k % 5])
		k //= 5
		i -= 1
	return ''.join((str(e) for e in reversed(ans)))
even = [0, 2, 4, 6, 8]
fdigits = [2, 4, 6, 8]
cs = [5]
i = 1
while cs[-1] < 10 ** 12 + 5:
	cs.append(cs[-1] + 5 ** i * 4)
	i += 1
T = int(input())
while T > 0:
	T -= 1
	k = int(input())
	print(kthmagical(k))


from math import log
t = int(input())
arr = [0, 2, 4, 6, 8]
for i in range(t):
	k = int(input())
	x = log(k, 5)
	m = int(x)
	a = []
	if m == 0:
		print(arr[k - 1])
	else:
		k -= 1
		while m >= 0:
			c = int(k / 5 ** m)
			k = k % 5 ** m
			a += [str(arr[c])]
			m -= 1
		if a[0] == '0':
			p = ''.join(a[1:])
		else:
			p = ''.join(a)
		print(p)


def sum1(a, b):
	return a + b

def num(n):
	if n == 0:
		return 0
	else:
		l = 10 * num(n // 5)
		m = n % 5 * 2
		return sum1(l, m)
t = int(input())
for i in range(0, t):
	k = int(input())
	k = k - 1
	print(num(k))
	print('\n')


from math import log
tcase = int(input())
for t in range(0, tcase):
	flag = 1
	n = int(input())
	if n == 5 or n == 25 or n == 125 or (n == 625) or (n == 3125) or (n == 15625) or (n == 78125) or (n == 390625) or (n == 1953125) or (n == 9765625) or (n == 48828125) or (n == 244140625) or (n == 1220703125) or (n == 6103515625) or (n == 30517578125) or (n == 152587890625) or (n == 762939453125):
		flag = 0
		n = n - 1
	m = int(log(n) / log(5))
	w = (2 * int((n - 1 - 5 ** m) / 5 ** m) % 8 + 2) * 10 ** m
	for i in range(0, m):
		w += 2 * int((n - 1 - 5 ** m) / 5 ** i) % 10 * 10 ** i
	if n == 1:
		print('0\n')
	elif n != 1 and flag == 0:
		print(int(w + 2))
	else:
		print(w)


def main():
	from sys import stdin, stdout
	l = [0, 2, 4, 6, 8]
	for _ in range(int(stdin.readline())):
		x = int(stdin.readline()) - 1
		g = ''
		while x:
			g = str(x % 5) + g
			x //= 5
		k = 0
		for i in g:
			k = k * 10 + l[int(i)]
		stdout.write(str(k) + '\n')
main()


T = int(input())
while T > 0:
	K = int(input())
	myK = K - 1
	if myK == 0:
		x = 0
		print(x)
	else:
		myList = []
		while myK > 0:
			myList.append(myK % 5)
			myK = myK // 5
		myList.reverse()
		length = len(myList)
		num = 0
		for i in range(length):
			num = myList[i] + num * 10
		print(num * 2)
	T = T - 1


def toDigits(n, b):
	if n == 0:
		return 0
	digits = []
	while n > 0:
		digits.insert(0, str(n % b))
		n = n // b
	return int(''.join(digits))
T = int(input())
for i in range(T):
	T = int(input())
	print(toDigits(T - 1, 5) * 2)


for t in range(int(input())):
	n = int(input())
	j = 5
	c = 1
	while True:
		if n // j == 0:
			j //= 5
			c -= 1
			break
		j *= 5
		c += 1
	num = ''
	for i in range(c):
		num += '1'
	num += '2'
	num = int(num)
	div = 10 ** c
	sum = op_sum = 0
	while True:
		if c == 0:
			break
		k = n // j - op_sum
		if n % j == 0:
			k -= 1
		op_sum += k
		j //= 5
		c -= 1
		sum += k * num
		num -= div
		div //= 10
		if c == 0:
			break
	k = n - (op_sum + 1)
	print(sum + k * 2)


converter = '01234'

def convert(n):
	if n < 5:
		return converter[n]
	return convert(n // 5) + converter[n % 5]
for i in range(int(input())):
	n = int(input()) - 1
	print(2 * int(convert(n)))


def base5(n):
	ans = 0
	i = 1
	while n != 0:
		ans = ans + n % 5 * i
		n = n // 5
		i *= 10
	return ans
for _ in range(int(input())):
	k = int(input())
	k -= 1
	i = base5(k)
	print(i * 2)


def mod5(n):
	if n == 0:
		return 0
	else:
		return 10 * mod5(n // 5) + n % 5

def ans(n):
	n -= 1
	return 2 * mod5(n)
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	print(ans(n))


for _ in range(int(input())):
	x = int(input())
	if x == 0:
		print(0)
	elif x == 1:
		print(0)
	else:
		x = x - 1
		s = ''
		p = x
		while p != 0:
			d = p % 5
			s += str(d)
			p = p // 5
		print(2 * int(s[::-1]))


from math import log, floor

def is_magical(N):
	while N != 0:
		if N % 10 % 2 != 0:
			return False
		N = N // 10
	return True
T = int(input())
for _ in range(T):
	K = int(input())
	ans = 0
	while K != 0:
		l5 = floor(log(K, 5))
		five_pow = 5 ** l5
		(K, quot) = (K % five_pow, K // five_pow)
		ans += 10 ** l5 * 2 * quot
	if ans % 10 == 0:
		l10 = 1
		while ans % 10 ** l10 == 0:
			l10 += 1
		sub = 1
		for _ in range(l10 - 1):
			sub = sub * 10 + 1
		sub += 1
		ans -= sub
	else:
		ans -= 2
	print(ans)


n = int(input())
for i in range(n):
	x = int(input())
	x = x - 1
	a = [0] * 100
	if x == 0:
		print('0')
	else:
		i = 0
		while x:
			a[i] = int(x % 5)
			x = int(x / 5)
			i = i + 1
		str1 = ''
		for j in range(0, i):
			str1 = str(2 * a[j]) + str1
		print(str1)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def to_base(n, base):
	if n == 0:
		return 0
	r = ''
	while n > 0:
		r = str(n % base) + r
		n //= 5
	return int(r)

def main():
	for _ in tr():
		n = to_base(nl() - 1, 5)
		print(n * 2)
main()


def special(n):
	L = []
	if n == 0:
		print(0)
	while n != 0:
		L.append(n % 5)
		n //= 5
	L = reversed([2 * i for i in L])
	print(*L, sep='')
t = int(input())
for _ in range(t):
	k = int(input())
	special(k - 1)


import math
import sys
global temp
global multilper
global sm
global i
sm = 0
multilper = 10
t = int(input())
while t > 0:
	i = 5
	t = t - 1
	k = int(input())
	sm = (k - 1) * 2
	while i >= 5 and i <= k:
		temp = k / float(i)
		temp = temp - 1
		temp = math.ceil(temp)
		sm = sm + temp * multilper
		multilper = multilper * 10
		i = i * 5
	multilper = 10
	print(int(sm))


t = int(input().strip())
while t:
	k = int(input().strip()) - 1
	if k == 0:
		print(0)
		t -= 1
		continue
	mu = 2
	car = 0
	no = k % 10
	ans = ''
	ch = k
	while ch != 0:
		temp = no * mu + car
		mu *= 2
		ans = str(temp % 10) + ans
		car = int(temp / 10) * 2
		ch = int(ch / 10)
		no = ch % 10
	if car:
		ch = car
		temp = car % 10
		while ch != 0:
			temp = ch % 10
			ans = str(temp) + ans
			ch = int(ch / 10) * 2
	print(ans)
	t -= 1


import sys
l = [0, 2, 4, 6, 8]

def main():
	t = int(input())
	while t > 0:
		k = int(input())
		print(result(k))
		t -= 1

def result(k):
	if k == 1:
		return 0
	else:
		if k % 5 == 0:
			a = k // 5
		else:
			a = k // 5
			a += 1
		ans = 10 * result(a) + 2 * (k + 4 - 5 * a)
		return ans
main()