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