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 Kth 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 Kth magical number.

-----Constraints-----
- 1 ≤ T ≤ 105
- 1 ≤ K ≤ 1012.

-----Subtasks-----
Subtask #1 : (20 points)
- 1 ≤ T ≤ 100
- 1 ≤ K ≤ 104.

Subtask 2 : (80 points) Original Constraints

-----Example-----
Input:
2
2
5

Output:
2
8

-----Explanation-----
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: interview

Starter code:

Solutions:
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')

for i in range(eval(input())):
    k=eval(input())
    while(i<k):
        i=i+1
    print(seq(i-1))


a=list()
l=list()
c=0
t=eval(input())
for i in range(0,t):
	k=eval(input())
	if(k<=len(a)):
		print(a[k-1])
	else:
		while(len(a)!=k):
			l=list(map(int,str(c)))
			flag=0
			
			for j in range(0,len(l)):
				if(l[j]%2!=0):
					flag=1
					break

			if(flag==0):
				a.append(c)
				c=c+2
			else:
				x=10**(len(l)-j-1)
				c=c+x

		print(a[k-1])

a=list()
l=list()
c=0
t=eval(input())
for i in range(0,t):
	k=eval(input())
	if(k<=len(a)):
		print(a[k-1])
	else:
		while(len(a)!=k):
			l=list(map(int,str(c)))
			flag=0
			
			for j in range(0,len(l)):
				if(l[j]%2!=0):
					flag=1
					break

			if(flag==0):
				a.append(c)
				c=c+2
			else:
				x=10**(len(l)-j-1)
				c=c+x

		print(a[k-1])

import math
def answer(n):
    n-=1
    if n>0:
        a=int(math.log(n,5))
    else:
        a=0
    total=0
    while a!=0:
        x=math.pow(5,a)
        g=n//x
        n=int(n%x)
        total+=2*math.pow(10,a)*g
        if n>0:
            a=int(math.log(n,5))
        else:
            a=0
    total+=2*(n)
    total=int(total)
    return total
T=int(input(''))
while T:
    T-=1
    n=int(input(''))
    print(answer(n))


a=list()
l=list()
c=0
t=eval(input())
for i in range(0,t):
	k=eval(input())
	if(k<=len(a)):
		print(a[k-1])
	else:
		while(len(a)!=k):
			l=list(map(int,str(c)))
			flag=0
			if(l[0]%2==0):
				for j in range(0,len(l)):
					if(l[j]%2!=0):
						flag=1
						break

			else:
				flag=1

			if(flag==0):
				a.append(c)
			x=10**(len(l)-1)
			if(l[0]%2==0):
				c=c+2
			else:
				c=c+x

		print(a[k-1])

def str_base(number, base):
   (d,m) = divmod(number,len(base))
   if d > 0:
      return str_base(d,base)+base[m]
   return base[m]

for _ in range(int(eval(input()))):
	n = int(eval(input()))
	print(str_base(n-1,'02468')) 

a=list()
l=list()
c=0
t=eval(input())
for i in range(0,t):
	k=eval(input())
	if(k<=len(a)):
		print(a[k-1])
	else:
		while(len(a)!=k):
			l=list(map(int,str(c)))
			flag=0
			for j in range(0,len(l)):
				if(l[j]%2!=0):
					flag=1
					break

			if(flag==0):
				a.append(c)
			c=c+2

		print(a[k-1])

a=list()
l=list()
c=0
t=eval(input())
for i in range(0,t):
	k=eval(input())
	if(k<=len(a)):
		print(a[k-1])
	else:
		while(len(a)!=k):
			l=list(map(int,str(c)))
			flag=0
			for j in range(0,len(l)):
				if(l[j]%2!=0):
					flag=1
					break

			if(flag==0):
				a.append(c)
			c=c+2

		print(a[k-1])

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=eval(input())
for i in range(t):
    k=eval(input())
    print(seq(k-1))


import math
t = eval(input())
for i in range(0,t):
	K = int(input())
	ans = []
	arr = [8,0,2,4,6]
	temp = 1
	i = 0
	while(temp > 0):
		k = arr[int(math.ceil(K/math.pow(5,i)))%5]
		i = i + 1
		temp = math.floor(float(K-1)/math.pow(5,i))
		ans.append(str(k))
	ans.reverse();
	print(''.join(ans))

test = eval(input())

for i in range(test):
	powOf5 = 762939453125
	coeff = 200000000000000000
	sum_ = 0;
	x = eval(input())
	while(x>25):
		if(x%powOf5):			# not 0
			sum_ += (x/powOf5)*coeff
			x %= powOf5
			powOf5 /= 5
		else:
			sum_ += coeff*((x-1)/powOf5)
			x = powOf5
			powOf5/=5
		coeff /= 10
		
		#print  str(sum_) + ' ' +  str(powOf5) + ' ' + str(coeff) 
	mod = x%5
	if mod ==0:
		mod = 5

	sum_ += (x-mod)*4 + (mod-1)*2

	print(sum_)



def cheffun(k):
    return 10 * cheffun(k // 5) + (k % 5) * 2 if k else 0
g=eval(input())
while (g>0):
    a=eval(input())
    k=a-1
    print(cheffun(k))
    g=g-1

def sort(d):
	if d==0:
		return 1
	if d==1:
		return 2
	if d==2:
		return 3

def sort1(s,e):
	if s<e:
		p=s*e
	return p

def function1(a):
    if a == 0: 
    	return
    for b in function1(a // 5): 
    	yield b
    c=a%5
    yield c

def function(m):
	#d=2*c
    return int(''.join(str(2 * c) for c in function1(m)) or '0')

t=eval(input())
while t>0:
	n=eval(input())
	a=0
	m=1
	p=0
	q=0
	r=0
	if m==1:
		p=1
		m=m+1
	if m==2:
		q=1
		m=m+1
	if m==3:
		r=1
		m=m+1
	if n==1:
		print(a)
	else:
		print(function(n-1))
	t=t-1
ml= [1,5,7,9]
s=0	
p=ml[s]
l=r+1
r=e=0
d= False
te=ml[s]
ml[s]=ml[r]
ml[r]=te