LUCKYN - Lucky Numbers

no tags 

 

Shrek and Kung Fu Panda once met after having no forthcoming prequels. They quickly noticed that both of them were superstitious and this helped them bond a lot.
Shrek believes that the number 4 is lucky and Kung Fu Panda believes that number 7 is lucky. You being their friend want to list down numbers in increasing order that consist only of 4 or 7.
The first few elements of the list are 4, 7, 44, 47, 74, 77, 444 ... You must answer the n-th (1-based, 4 is the 1st term of the sequence)

 

Shrek and Kung Fu Panda once met after having no forthcoming prequels. They quickly noticed that both of them were superstitious and this helped them bond a lot.

Shrek believes that the number 4 is lucky and Kung Fu Panda believes that number 7 is lucky. You being their friend want to list down numbers in increasing order that consist only of 4 or 7.

The first few elements of the list are 4, 7, 44, 47, 74, 77, 444 ... You must answer the n-th (1-based, 4 is the 1st term of the sequence)

 

 

Input

 

The first line contains the number of test-cases T 

The following T-lines contains an integer n.

T <= 10,000

n <= 1000,000,000

 

Output

 

Print the n-th term in the sequence of lucky numbers

 

Example

Input:
6
1
20
300
4000
50000
1000000000


Output:
4
4747
44747747
77774744447
744447747474447
77477744774747744747444444447

hide comments
nadstratosfer: 2018-06-17 07:39:46

Enjoyed figuring this out.

Siya: 2014-11-10 10:25:54

Can you provide any tricky test cases because i have checked almost all manually and finding my solution correct

Mistake was mine only :)Finally AC

Last edit: 2014-11-10 10:49:25
Naveen Kumar: 2012-10-05 06:03:10

i m getting wrong answer, why?
while i cheked for all test cases.i m nt getting where i have missed?


Added by:.:: Pratik ::.
Date:2011-03-07
Time limit:1.528s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64