Matchsticks

Interview

Time limit1sMemory limit128 MB

Summary

Given a number of matchsticks, find the smallest and largest positive numbers (no leading zero) that can be formed using exactly that many matchsticks based on per-digit costs.

Level: Medium4 of 10
Topics: Dynamic programming, Greedy, Math
Solved: No attempts yet

Problem

Matchsticks are an ideal tool for representing numbers. Each digit of a decimal number is built from a fixed number of matchsticks according to the table below.

Digit	Matchsticks
0	6
1	2
2	5
3	5
4	4
5	5
6	6
7	3
8	7
9	6

Given a number of matchsticks, write a program that finds the smallest number and the largest number you can build using all of the matchsticks.

Input

The first line contains the number of test cases, at most 100. Each test case consists of a single line containing the number of matchsticks $n$ . ( $2 \le n \le 100$ )

Output

For each test case, print the smallest number and the largest number that can be built using all of the given matchsticks, separated by a space, on one line. Both numbers must be positive and must not start with a zero.

Examples3

Example 1
Input
```
4
3
6
7
15
```
Expected output
```
7 7
6 111
8 711
108 7111111
```
Example 2
Input
```
1
2
```
Expected output
```
1 1
```
Example 3
Input
```
1
4
```
Expected output
```
4 11
```