You are given several queries. In the i-th query you are given a single positive integer ni. You are to represent ni as a sum of maximum possible number of composite summands and print this maximum number, or print -1, if there are no such splittings.

An integer greater than 1 is composite, if it is not prime, i.e. if it has positive divisors not equal to 1 and the integer itself.

Input

The first line contains single integer q (1 ≤ q ≤ 105) — the number of queries.

q lines follow. The (i + 1)-th line contains single integer ni (1 ≤ ni ≤ 109) — the i-th query.

Output

For each query print the maximum possible number of summands in a valid splitting to composite summands, or -1, if there are no such splittings.

Examples

Input

1
12


Output

3


Input

2
6
8


Output

1
2


Input

3
1
2
3


Output

-1
-1
-1

Note

12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, but the first splitting has the maximum possible number of summands.

8 = 4 + 4, 6 can't be split into several composite summands.

1, 2, 3 are less than any composite number, so they do not have valid splittings.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.Vector;



public class Solve {
	static int k1,k2;
	static int kk,n ,m;
	static int []trees ;
	static int[][] a;
	static long dp[][][]=new long[100+2][100+2][100+1];
	public static void main(String[] args) throws IOException{
		FastScanner sc = new FastScanner();
	    PrintWriter out = new PrintWriter(System.out);
	     int q = sc.nextInt();
	     
	     for(int i=0;i<q;i++)
	     {
	    	 int x = sc.nextInt();
	    	 if(x<4 || x==5 || x==7 ||x==11  )
	    		 out.println(-1);
	    	 else
	    	 if(x==4)
	    		 out.println(1);
	    	 else
	    	 if(x%4==0)
	    		 out.println(x/4);
	    	 else
	    	 if(x%4==1)
	    		 out.println(1+(x-9)/4);
	    	 else
	    	 if(x%4==2)
	    		 out.println(1+(x-6)/4);
	    	 else
	    	 if(x%4==3)
	    		 out.println(2+(x-6-9)/4);
	    	 
	    	 
	    	 
	    	 
	    	 
	     }
	     out.flush();
	     out.close();
	    
	     
	     
	
	}
	private static boolean isprim(int i) {
		for(int j=2;j*j<=i+2;j++)
			if(i%j==0)
				return false;
		return true;
	}
	

	
	
	














}
	















































































class pair implements Comparable{
	int x ,y,z;
	pair(int x,int y,int z)
	{
		this.x=x;
		this.y=y;
		this.z=z;
	}
	@Override
	public int compareTo(Object arg0) {
		
		pair u =((pair)arg0);
		
		return -this.z+u.z;
	}
}
 	


	    
	    
	    



class FastScanner {




    BufferedReader br;
    StringTokenizer st;

    public FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public FastScanner(String s) {
        try {
            br = new BufferedReader(new FileReader(s));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    String nextToken() {
        while (st == null || !st.hasMoreElements()) {
            try {
            	
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(nextToken());
    }

    long nextLong() {
        return Long.parseLong(nextToken());
    }

    double nextDouble() {
        return Double.parseDouble(nextToken());
    }
 

}