Birthday Numbers I

Time limit1sMemory limit256 MB

Summary

Find the numerically smallest number made only of digits 3, 5 and 8 whose digits add up to N, or -1 when none exists.

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

Problem

Seunghyun was born on 5 March 1998, so he likes the digits 3, 5 and 8 that appear in his date of birth. He decided to call a positive integer a birthday number when its decimal representation consists only of the digits 3, 5 and 8. For example 3, 533 and 858553 are birthday numbers, while 3518, 1642 and 88808 are not.

Given a positive integer $N$ , find the smallest birthday number whose digits sum to $N$ .

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100$ ). Each of the next $T$ lines contains one positive integer $N$ ( $1 \le N \le 1\,000\,000$ ).

Output

For each test case, print on its own line the smallest birthday number whose digits sum to $N$ . If no such number exists, print -1.

Examples4

Example 1
Input
```
3
11
16
12
```
Expected output
```
38
88
3333
```

Example 2

Input

Expected output

Example 3
Input
```
4
1
2
4
7
```
Expected output
```
-1
-1
-1
-1
```

Example 4

Input

Expected output