Recently RAW have been having weird problems with their supercomputer 'The PARAM'. Today, They recieved a note from hackers that they have infected 'The PARAM' with a virus. In addition the note had the number 'k' printed on it. After doing some calculations, RAW agents found out that the only way to remove that virus is the largest 'Killer' Number having 'k' digits.

A 'Killer' Number has:

1. Only 3 and 5 as its digits.
2. Number of times 3 appears is divisible by 5.
3. Number of times 5 appears is divisible by 3.

Meanwhile, the counter to destruction of ‘The PARAM' is running very fast. Can you save ‘The PARAM’ and find the key before RAW agents?

Input

1st line will contain an integer T, the number of test cases, followed by T lines, each line containing an integer N i.e. the number of digits in the number

1 <= T <= 20
1 <= N <= 100000

Output

Largest Killer number having N digits. If no such number exists, you tell RAW agents that they are wrong and print ‘-1’.

Example

Input:
3
1
3
11

Output:
-1
555
55555533333

Explanation

• For N = 1, there is no such number.
• For N = 3, 555 is only possible number.
• For N = 11, 55555533333 and all of permutations of digits are valid numbers, among them, the given number is the largest one.