You are given exactly n identical matchsticks. Your task is to form a positive integer using all of these matchsticks. Each digit from 0 to 9 requires a specific number of matchsticks to be formed.
Rules:
You must use exactly n matchsticks.
The resulting number must be a positive integer (no leading zeros).
If it is impossible to form any positive integer, output -1.
Find the smallest possible integer that can be formed.
Input
The first line contains an integer T (1 \le T \le 10^3), the number of test cases.
Each test case consists of a single integer n (1 \le n \le 10^5), representing the number of matches available.
Output
For each test case, output the smallest positive integer that can be formed using all n matches. Since the number can be very large, output it as a string. If no such number exists, output -1.
Examples
| standard input | standard output |
|---|
| 3
2
6
15
| 1
6
108
|
Note
The number of matchsticks required for each digit is based on a standard seven-segment display:
2 matches: 1
3 matches: 7
4 matches: 4
5 matches: 2, 3, 5
6 matches: 0, 6, 9
7 matches: 8