In this article we will try to help Sherlock Holmes, the most famous detective hero. Sherlock Holmes against supercomputer.

Scenario

Sherlock Holmes becomes paranoid about his arch-nemesis Moriarty. All his efforts to suppress Moriarty have been wasted. Sherlock is currently working on a problem with Watson. Watson has recently stated that the CIA’s supercomputer, Beast, is facing strange problems.

This afternoon, Sherlock receives a note from Moriarty stating that he has infiltrated the Beast by means of a virus. Also, there are N numbers on the note. After performing some calculations, Sherlock solved that the maximum reasonable value of the key required to remove the virus would be N digits.

The most reasonable number should have the following characteristics:

• Only digits 3 or 5 can be used in digits. There should be no other figures.
• The number 3 used a number of times can be divided by 5.
• The number 5 used a number of times can be divided by 3.

In the meantime, the counter works very fast to destroy the Beast. Can we find the key to saving Beast? Can we do that before Sherlock?

Input Format: Line 1 will be an integer (T) to represent the number of test cases.

Output Format: Our largest reasonable number will be N digits. If a numeral is not entered, Sherlock will say that it is the wrong entry and type -1 on the screen.

Limitations

• 1≤T≤20
• 1≤N≤100000

Explanation

• For N = 1, it does not apply.
• For N = 3, 555 is the only possible number.
• For N = 5, 33.333 is the only possible number.
• N = 11, 55555533333 is the largest number of possibilities that can be generated with these numbers.

Solution

/*
 * Coding by hkucuk
 */
import java.io.*;

public class SolutionSTB {

    public static void main(String[] args) throws IOException {

        StringBuffer sb = new StringBuffer();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        byte[] mults = new byte[]{0, 2, 4, 1, 3, 0, 2, 4, 1, 3};

        for(int T = Integer.parseInt(br.readLine()); T > 0; T--){

            String S = br.readLine();
            int N = Integer.parseInt(S);
            
            // How many groups of 5 to delete
            int G = mults[S.charAt(S.length()-1) - 48];
            N -= 3*G;
            
            // If the number is too small
            if (N < 0){
                sb.append("-1\n"); continue;
            }
            
            // Adding 5 groups
            for(G += 5*(N/15); G > 0; G--){
                sb.append("555");
            }
            
            // Adding 3 groups
            for(G = (N%15)/5; G > 0; G--){
                sb.append("33333");
            }
            
            // Adding new rows
            sb.append("\n");
        }
        
        System.out.print(sb);
    }
}

Sample Input

4
1
3
5
11

Sample Output

-1
555
33333
55555533333