LUCKYN - Lucky Numbers

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

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

hide comments
2018-06-17 07:39:46
Enjoyed figuring this out.
2014-11-10 10:25:54 Siya
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
2012-10-05 06:03:10 Naveen Kumar
i m getting wrong answer, why?
while i cheked for all test cases.i m nt getting where i have missed?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.