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.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

//import Number_theory.pair;

public class hacker49 {
	public static int r1=0;
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
	static class pair{
		private long cnt;
		private long[] fq;
		private long[] pref;
		pair(){
			fq=new long[41];
			pref=new long[41];
			cnt=(long)0;
		}	
	}
	
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
		FastReader s=new FastReader();
        int q=s.nextInt();
        while(q>0) {
        	long n=s.nextLong();
        	if(n==1 || n==2 || n==3 || n==11) {
        		out.println(-1);
        	}else {
        		if(n%2==0) {
        			out.println(n/4);
        		}else {
        			if(n<9) {
        				out.println(-1);
        			}else {
        				long d=n-9;
        				if(d==6) {
        					out.println(2);
        				}else {
        					out.println((d/4)+1);
        				}
        			}
        		}
        	}
        	q--;
        }
        		
        out.close();
	}
	
	static long mod=1000000007;
//	for(int i=2;i<=100000;i++) {
		
//	}
	static long[] f=new long[200001];
	static void fac() {
		f[0]=1;
		f[1]=1;
		for(long i=2;i<=200000;i++) {
			f[(int) i]=(i*f[(int) (i-1)])%mod;
		}
	}
	static int get=0;
	static int h=0;
	static void  ans(int b,int sum) {
		if(b==0) {
			if(sum==get) {
				h++;
			}
			return;
		}else {
			ans(b-1,sum+1);
			ans(b-1,sum-1);
			
		}
		
		
	}
	static int lower(char[] b,int n) {
		int l=3;
		int r=n;
//		for(int i=0;i<32;i++) {
		while(r!=l) {
			int mid=(l+r)/2;
			if(good(b,mid)) {
				r=mid;
			}else {
				l=mid+1;
			}
		}
//		}
		if(r==(n)) {
			return 0;
		}else {
			return (r);
		}
	}
	static boolean good(char[] b,int k) {
		int[] a=new int[4];
		int l=1;
		int r=k+1;
//		System.out.println(k);
		int n=b.length;
		for(int i=1;i<=k;i++) {
			a[(int)(b[i]-'0')]++;
		}
		if(a[1]>0 && a[2]>0 && a[3]>0) {
			return true;
		}else {
			boolean p=false;
			while(r<n) {
				a[(int)(b[l]-'0')]--;
				a[(int)(b[r]-'0')]++;
				if(a[1]>0 && a[2]>0 && a[3]>0) {
					p=true;
					break;
				}
//				System.out.println(1);
				l++;
				r++;
			}
			if(p) {
				return true;
			}
			return false;
		}
	}
	static ArrayList<Long> d=new ArrayList<>(); 
	public static long res=1;
	public static void pf(long n) {
		
		 for (long i=1; i<=Math.sqrt(n); i++)
	        {
	            if (n%i==0)
	            {
	                // If divisors are equal, print only one
	                if (n/i == i) {
//	                    System.out.print(" "+ i);
	                	d.add(i);
	                }else { // Otherwise print both
	                    d.add(i);
	                    d.add(n/i);}
	            }
	        }	
	}

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	public static void Create(long[] a,pair[] segtree,int low,int high,int pos) {
		if(low>high) {
			return;
		}
		if(low==high) {
			for(int i=1;i<=40;i++) {
				if(i==a[low]) {
					segtree[pos].fq[i]=1;
				}else {
					segtree[pos].fq[i]=0;
				}
				segtree[pos].pref[i]=segtree[pos].fq[i]+segtree[pos].pref[i-1];
			}
			
			return ;
		}
		int mid=(low+high)/2;
		Create(a,segtree,low,mid,2*pos);
		Create(a,segtree,mid+1,high,2*pos+1);
		pair a3=new pair();
		for(int i=1;i<=40;i++) {
			a3.fq[i]=segtree[2*pos].fq[i] +segtree[2*pos+1].fq[i];
			a3.pref[i]=a3.fq[i]+a3.pref[i-1];
		}
		for(int i=1;i<=40;i++) {
		a3.cnt+=segtree[2*pos].fq[i]*segtree[2*pos+1].pref[i-1];
		}
		a3.cnt+=segtree[2*pos].cnt+segtree[2*pos+1].cnt;
		for(int i=1;i<=40;i++) { 
		segtree[pos].fq[i]=a3.fq[i];
		 segtree[pos].pref[i]=a3.pref[i];} 
		segtree[pos].cnt=a3.cnt;
	}
	public static void update(pair[] segtree,int low,int high,int index,int pos,int val) {
		
		if(low==high && low==index) {
			for(int i=1;i<=40;i++) {
				if(i==val) {
					segtree[pos].fq[val]=1;
				}else {
					segtree[pos].fq[i]=0;
				}
				segtree[pos].pref[i]=segtree[pos].fq[i]+segtree[pos].pref[i-1];
			}
			segtree[pos].cnt=(long)0;
			return;
		}
			int mid=(high+low)/2; 
			if(index<=mid) {
			update(segtree,low,mid,index,2*pos,val);}else {
			 update(segtree,mid+1,high,index,2*pos+1,val);}
			pair a3=new pair();
			for(int i=1;i<=40;i++) {
				a3.fq[i]=segtree[2*pos].fq[i] +segtree[2*pos+1].fq[i];
				a3.pref[i]=a3.fq[i]+a3.pref[i-1];
			}
			for(int i=1;i<=40;i++) {
			a3.cnt+=segtree[2*pos].fq[i]*segtree[2*pos+1].pref[i-1];
			}
			a3.cnt+=segtree[2*pos].cnt+segtree[2*pos+1].cnt;
			for(int i=1;i<=40;i++) { 
			segtree[pos].fq[i]=a3.fq[i];
			 segtree[pos].pref[i]=a3.pref[i];} 
			segtree[pos].cnt=a3.cnt;
	}
	public static pair query(pair[] segtree,int low,int high,int qlow,int qhigh ,int pos) {
		if(low>=qlow && high<=qhigh) {
			return segtree[pos];
		}
		if(qhigh<low || qlow>high) {
			return new pair();
		}
		int mid=(low+high)/2;
		
	  pair a1=query(segtree,low,mid,qlow,qhigh,2*pos);
	  pair a2=query(segtree,mid+1,high,qlow,qhigh,2*pos+1);
	  pair a3=new pair();
	  for(int i=1;i<=40;i++) {
			a3.fq[i]=a1.fq[i] +a2.fq[i];
			a3.pref[i]=a3.fq[i]+a3.pref[i-1];
		}
		for(int i=1;i<=40;i++) {
			a3.cnt+=a1.fq[i]*a2.pref[i-1];
		}
		a3.cnt+=a1.cnt+a2.cnt;
	  return a3;
	  
	}
	
	public static long nextPowerOf2(long n) 
	{ 
	    n--; 
	    n |= n >> 1; 
	    n |= n >> 2; 
	    n |= n >> 4; 
	    n |= n >> 8; 
	    n |= n >> 16; 
	    n++;     
	    return n; 
	} 
	}
