Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

In order to sharpen their basic arithmetic skills, kids often try to represent numbers using match sticks. As one is only given a limited number, one student is curious how high he can count with his matches. Each one digit number is represented as follows: - number 8 uses seven matches. - numbers 0, 6 and 9 each use six matches. - numbers 2, 3 and 5 each use five matches. - numbers 4 and 7 each use four matches. - number 1 uses two matches. Given the number of matches he has at his disposal, Can you tell me the smallest positive integer that cannot be represented?

Input

The first line of the input will be a integer to represent the number of test cases. For each case there is only one line contains only one integer N denoting the number of matches. ( 1 <= N <= 10^5 ) There is a blank line before each test case.

Output

For each test case output the answer on a line: The smallest positive integer that cannot be represented.

Sample Input

3 1 9 11

Sample Output

1 20 28

Source