F. Not A Giveaway
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Warning: Not A Giveaway.

You have a large electronic screen which can display up to $$$1000000007$$$ decimal digits. each place for a digit consists of $$$7$$$ segments which can be turned on and off to compose different digits. The following picture describes how you can display all 10 decimal digits:

As you can see, different digits may require different numbers of segments to be turned on. For example, if you want to display $$$1$$$, you have to turn on $$$2$$$ segments of the screen, and if you want to display $$$8$$$, all $$$7$$$ segments of someplace to display a digit should be turned on.

Your task is to find the minimum number you can show on display by turning exactly $$$N$$$ segments on. You can't have leading zeroes in the number, that means the first digit of your number can be $$$0$$$ if and only if the total number you're showing is $$$0$$$.

Input

The first line contains one integer $$$t (1 \leq t \leq 10^4)$$$ — the number of test cases in the input.

Then the test cases follow, each of them is represented by a separate line containing one integer $$$n (2 \leq n \leq 10^6)$$$ — the number of segments that should be turned on in the corresponding test case.

It is guaranteed that the sum of $$$n$$$ over all test cases in the input does not exceed $$$10^6$$$.

Output

For each test case, print the smallest integer that can be displayed by turning on exactly $$$n$$$ segments of the screen without leading zeores. Note that the answer may not fit in the standard $$$32$$$-bit or $$$64$$$-bit integral data type.

Example
Input
3
2
7
16
Output
1
8
188