408493: GYM103150 G Segmentation Fault

G. Segmentation Faulttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have an infinitely long digital panel. Each digit consists of $$$7$$$ segments, which can be turned on or off to display different numbers. The picture shows how all $$$10$$$ decimal digits are displayed.

In this picture, the segments that are turned on are marked black. Initially all segments in the panel are off. You want to turn on exactly $$$n$$$ segments to display a positive integer (without leading zeroes). Find the minimum and maximum possible values of this integer.Input

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

The only line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output two space-separated positive integers — the minimum and maximum possible values of the number on the panel, respectively.

ExampleInput

3
2
3
4

Output

1 1
7 7
4 11

Note

By turning on two segments, the only number you can display is $$$1$$$.

By turning on three segments, the only number you can display is $$$7$$$.

By turning on four segments, the smallest number you can display is $$$4$$$ and the largest number you can display is $$$11$$$.