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.
//Lucky Division

import java.io.*;
	import java.math.BigInteger;
	import java.math.RoundingMode;
	import java.text.DecimalFormat;
	import java.util.*;
	
/**
 * @author Aayush Agrawal
 *
 */
public class some {
		
	
		static double eps=(double)1e-6;
		static long mod=(int)1e9+6;
		
		public static void main(String args[]) throws IOException{
			InputReader sc = new InputReader(System.in);
			OutputStream outputStream = System.out;
			PrintWriter out = new PrintWriter(outputStream);
			//-------------------------------------
			
			int t = sc.nextInt();
			for(int i=0; i<t; i++)
			{
				int n = sc.nextInt();
				out.println(cal(n));
			}
			
			//-------------------------------------
			out.close();
		}
		
		static int cal(int n)
		{
			int ans=0;
			if(n<4)
				ans = -1;
			else
			{
				int x = n%4;
				if(x==0)
					ans = n/4;
				else if(x==1)
				{
					if(n==5)
						ans = -1;
					else if(n==9)
						ans = 1;
					else
					{
						n-=9;
						ans+=1;
						ans+=n/4;
					}
				}
				else if(x==2)
				{
					if(n==6)
						ans = 1;
					else
					{
						n-=6;
						ans+=1;
						ans+=n/4;
					}
				}
				else
				{
					if(n==7 || n==11)
						ans = -1;
					else
					{
						n-=15;
						ans+=2;
						ans+=n/4;
					}
				}
			}
			return ans;
		}
		
		static void pythagoras(long a, PrintWriter out)
		{
			if(a>=3)
			{
				long b, c;
				
				if(a%2==0)
				{
					b = (a/2)*(a/2) - 1;
					c = b+2;
				}
				else
				{
					b = (a*a -1)/2;
					c = b+1;
				}
				out.println(b + " " + c);
			}
			else
				out.println(-1);
		}
		
		static boolean[] my_sieve(boolean[] b)
		{
			for(int i=2; i<b.length; i++)
			{
				if(!b[i])
				{
					for(int j = 2*i; j<b.length; j = j+i)
						b[j] = true;
				}
			}
			return b;
		}
		
		
		
		static boolean check(int x)
		{
			while(x!=0)
			{
				if(x%10==4 || x%10==7)
					x = x/10;
				else
					return false;
			}
			return true;
		}
		
		static class Pair implements Comparable<Pair> {
			int a, b;

			Pair(int a, int b) {
				this.a = a;
				this.b = b;
			}

			public int compareTo(Pair o) {
				// TODO Auto-generated method stub
				if (this.a != o.a)
					return Integer.compare(this.a, o.a);
				else
					return Integer.compare(this.b, o.b);
				//return 0;
			}

			public boolean equals(Object o) {
				if (o instanceof Pair) {
					Pair p = (Pair) o;
					return p.a == a && p.b == b;
				}
				return false;
			}

			public int hashCode() {
				return new Integer(a).hashCode() * 31 + new Integer(b).hashCode();
			}

			public String toString() {
				return a + " " + b;
			}
		}
		
		static int[] sieve(int n,int[] arr)
		{
			for(int i=2;i*i<=n;i++)
			{
				if(arr[i]==0)
				{
					for(int j=i*2;j<=n;j+=i)
						arr[j]=1;
				}
			}
			return arr;
		}
		
		static boolean isPal(String s)
		{
			for(int i=0, j=s.length()-1;i<=j;i++,j--)
			{
				if(s.charAt(i)!=s.charAt(j)) return false;
			}
			return true;
		}
		public static String rev(String s)
		{
			StringBuilder sb=new StringBuilder(s);
			sb.reverse();
			return sb.toString();
		}
		    
		static long lcm(long a, long b)
		{
		    return a * (b / gcd(a, b));
		}
		
		static long gcd(long a, long b)
		{
		    while (b > 0)
		    {
		        long temp = b;
		        b = a % b; // % is remainder
		        a = temp;
		    }
		    return a;
		}
		static long modulo(long a,long b,long c) {
			long x=1;
			long y=a;
			while(b > 0){
				if(b%2 == 1){
					x=(x*y)%c;
				}
				y = (y*y)%c; // squaring the base
				b /= 2;
			}
			return  x%c;
		}
		public static void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
		
		static long sort(int a[]) {
			int n = a.length;
			int b[] = new int[n];
			return mergeSort(a, b, 0, n - 1);
		}

		static long mergeSort(int a[], int b[], long left, long right) {
			long c = 0;
			if (left < right) {
				long mid = left + (right - left) / 2;
				c = mergeSort(a, b, left, mid);
				c += mergeSort(a, b, mid + 1, right);
				c += merge(a, b, left, mid + 1, right);
			}
			return c;
		}

		static long merge(int a[], int b[], long left, long mid, long right) {
			long c = 0;
			int i = (int) left;
			int j = (int) mid;
			int k = (int) left;
			while (i <= (int) mid - 1 && j <= (int) right) {
				if (a[i] <= a[j]) {
					b[k++] = a[i++];
				} else {
					b[k++] = a[j++];
					c += mid - i;
				}
			}
			while (i <= (int) mid - 1)
				b[k++] = a[i++];
			while (j <= (int) right)
				b[k++] = a[j++];
			for (i = (int) left; i <= (int) right; i++)
				a[i] = b[i];
			return c;
		}  
		
	
		static class InputReader {
    		public BufferedReader reader;
    		public StringTokenizer tokenizer;
     
    		public InputReader(InputStream inputstream) {
    			reader = new BufferedReader(new InputStreamReader(inputstream));
    			tokenizer = null;
    		}
     
    		public String nextLine(){
    			String fullLine=null;
    			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
    				try {
    					fullLine=reader.readLine();
    				} catch (IOException e) {
    					throw new RuntimeException(e);
    				}
    				return fullLine;
    			}
    			return fullLine;
    		}
    		public String next() {
    			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
    				try {
    					tokenizer = new StringTokenizer(reader.readLine());
    				} catch (IOException e) {
    					throw new RuntimeException(e);
    				}
    			}
    			return tokenizer.nextToken();
    		}
    		public long nextLong() {
    			return Long.parseLong(next());
    		}
    		public int nextInt() {
    			return Integer.parseInt(next());
    		}
    	}
    	
    }