Pratyush, a six year old kid has just learnt how to write 1 through 1000 in decimal number system(DNS). Being a very curious kid, he made some modifications in DNS and removed the digits 0 through 3 and 7 through 9. So the only digits remaining to be used are 4, 5 and 6. He started enumerating numbers with these digits in increasing order viz. 4, 5, 6, 44, 45, 46, 54, 55, 56, 64, 65, 66, 444 ... and so on. Ecstatic with his discovery he named it Pratyush Number System(PNS). Then he had an idea. He called his 10 year old brother Keshav and put forward a problem for him. Given a number n in DNS, give the nth number that appears in PNS. For example for n=3, answer is 6. For n=13, answer is 444.

Input

First line of input is a single integer T, after which T test cases follow. Each test case is a line with a single integer n in decimal number system.

Output

For each test case output the corresponding number in PNS followed by a new line character.

Constraints

1<= t <= 200
1 <= n <= 10^25

Example

Input:
5
3
13
45
64
1000000000

Output:
6
444
4456
4664
5446456455646565564

见题面

见题面