UVA - 11342 - Three-square

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;




public class Main {

    public static void main(String[] args) throws IOException{
       InputStreamReader isr=new InputStreamReader(System.in);
       BufferedReader br=new BufferedReader(isr);
       int num[]=new int[50*1000+1];
       int cases= Integer.parseInt(br.readLine());
       for(int i=0;i<225;i++){
           int temp=0;
            for(int j=0;j<225;j++){
                 for(int z=0;z<225;z++){
                     temp=(z*z)+(j*j)+(i*i);
                     if(temp>50000)
                         break;
                     if(num[temp]==0){
                         num[temp]=(z*1000*1000)+(j*1000)+i;
                     }
                 }
            }
       }
       StringBuilder out = new StringBuilder("");
       for(int i=0;i<cases;i++){
           int temp=Integer.parseInt(br.readLine());
           if(num[temp]!=0){
                int m=num[temp];
                int rem=m%1000;
                m/=1000;
                out.append(rem).append(" ");
                rem=m%1000;
                m/=1000;
                out.append(rem).append(" ");
                rem=m%1000;
                out.append(rem);
           }else{
               out.append("-1");
           }
           out.append("\n");
       }
       System.out.print(out);
    }
}