Sherlock and the Beast

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;


class Solution
{
    static void Main(String[] args)
    {
        int numsCount = Convert.ToInt32(Console.ReadLine());
        for(int i = 0; i < numsCount; i++)
        {
            int n = Convert.ToInt32(Console.ReadLine());

            if(n % 3 == 0)
            {
                Console.WriteLine(new string('5', n));
            }
            else if(n%5 == 0)
            {
                Console.WriteLine(new string('3', n));
            }
            else
            {
                bool isFound = false;

                for(int j = n / 3; j >= 0; j--)
                {
                    if((n - (j * 3)) % 5 == 0)
                    {
                        Console.WriteLine("{0}{1}", new string('5', j * 3), new string('3', n - j * 3));
                        //Console.WriteLine("n-j ={0}, n = {1}, j = {2}", n-j, n, j);
                        isFound=true;
                        break;
                    }
                }
                if(!isFound)
                {
                    for(int j = n / 5; j >= 0; j--)
                    {
                        if((n - (j * 5)) % 3 == 0)
                        {
                            Console.WriteLine("{0}{1}", new string('3', j * 5), new string('5', n - j * 5));
                        //Console.WriteLine("n-j ={0}, n = {1}, j = {2}", n-j, n, j);
                            isFound=true;
                            break;
                        }
                    }
                }
                if(!isFound)
                {
                    Console.WriteLine(-1);
                }
            }
        }
    }
}