## 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```