Hey man, I didnt know how StringBuilder worked, but still got the solution reducing the number of iterations.

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int t = in.nextInt();

    for (int i=0;i<t;i++){

        int n = in.nextInt();
        String sol3 = "", sol5 = "";
        String staux = "555";

        while(n>0){
            if (n%3==0)
                break;                                    
            else{                    
                sol3+="33333";
                n-=5;                    
            }
        }            

        while (n>0){

            if (staux.length()<=n){
                sol5+=staux;
                n-=staux.length();
                staux+=staux;
            }
            else
                if (n<3) 
                    break;
                else
                    staux="555";

        }

        if (n==0)
            System.out.println(sol5+sol3);
        else
            System.out.println(-1);

    } 
}

Still much better using Stringbuilder, but not impossible with strings ;) Thanks for the info.