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.IOException;
import java.io.*;
import java.util.*;
public class aav {
	public static void main(String[] args) throws IOException 
	{
		int q=i();
		for(int y=0;y<q;y++)
		{
			int h=0;
			int n=i();
			if(n%2==1)
			{
				h=1;
				if(n>9)
				{
				n=n-9;	
				
				
				
				if(n%4==0)
				{
					h=h+n/4;
					out.println(h);
				}
				else
				{
					if(n==2)
					{
						out.println(-1);
					}
					else
					{
						h=h+1;
						h=h+(n-6)/4;
						out.println(h);
					}
				}
				
				
				
				
				
				
				
				
				
				}
				else
				{
				if(n==9)
				{
					out.println(1);
				}
				else
				{
					out.println(-1);
				}
				}
			}
			else
			{
				if(n%4==0)
				{
					h=n/4;
					out.println(h);
				}
				else
				{
					if(n==2)
					{
						out.println(-1);
					}
					else
					{
						h=1;
						h=h+(n-6)/4;
						out.println(h);
					}
				}
			}
			
		}
		out.close();
	}
	
	static InputReader in = new InputReader(System.in);
	    static OutputWriter out = new OutputWriter(System.out);
	    
	    static int i()
	    {
	    	return in.readInt();
	    }
	    
	    static long l()
	    {
	    	return in.readLong();
	    }
	    
	    static double d()
	    {
	    	return in.readDouble();
	    }
	    
	    static String s()
	    {
	    	return in.readString();
	    }
	    
	    static void Iarr( int[] array, int no )
	    {
	    	for( int i=0 ; i<no ; i++ )
	    	{
	    		array[i] = i(); 
	    	}
	    }
	    
	    static void Larr( long[] array, int no )
	    {
	    	for( int i=0 ; i<no ; i++ )
	    	{
	    		array[i] = l(); 
	    	}
	    }
	    
	    static void Darr( double[] array, int no )
	    {
	    	for( int i=0 ; i<no ; i++ )
	    	{
	    		array[i] = d(); 
	    	}
	    }
	    
	    static void Sarr( String[] array, int no )
	    {
	    	for( int i=0 ; i<no ; i++ )
	    	{
	    		array[i] = s(); 
	    	}
	    }
	    
	    private static class InputReader
	    {
	        private InputStream stream;
	        private byte[] buf = new byte[1024];
	        private int curChar;
	        private int numChars;
	        private SpaceCharFilter filter;
	 
	        public InputReader(InputStream stream)
	        {
	            this.stream = stream;
	        }
	 
	        
	        
	        
	        
	        
	        
	        public int read()
	        {
	            if (numChars == -1)
	                throw new InputMismatchException();
	            if (curChar >= numChars)
	            {
	                curChar = 0;
	                try
	                {
	                    numChars = stream.read(buf);
	                } catch (IOException e)
	                {
	                    throw new InputMismatchException();
	                }
	                if (numChars <= 0)
	                    return -1;
	            }
	            return buf[curChar++];
	        }
	 
	        public int readInt()
	        {
	            int c = read();
	            while (isSpaceChar(c))
	                c = read();
	            int sgn = 1;
	            if (c == '-')
	            {
	                sgn = -1;
	                c = read();
	            }
	            int res = 0;
	            do
	            {
	                if (c < '0' || c > '9')
	                    throw new InputMismatchException();
	                res *= 10;
	                res += c - '0';
	                c = read();
	            } while (!isSpaceChar(c));
	            return res * sgn;
	        }
	 
	        public String readString()
	        {
	            int c = read();
	            while (isSpaceChar(c))
	                c = read();
	            StringBuilder res = new StringBuilder();
	            do
	            {
	                res.appendCodePoint(c);
	                c = read();
	            } while (!isSpaceChar(c));
	            return res.toString();
	        }
	        public double readDouble() {
	            int c = read();
	            while (isSpaceChar(c))
	                c = read();
	            int sgn = 1;
	            if (c == '-') {
	                sgn = -1;
	                c = read();
	            }
	            double res = 0;
	            while (!isSpaceChar(c) && c != '.') {
	                if (c == 'e' || c == 'E')
	                    return res * Math.pow(10, readInt());
	                if (c < '0' || c > '9')
	                    throw new InputMismatchException();
	                res *= 10;
	                res += c - '0';
	                c = read();
	            }
	            if (c == '.') {
	                c = read();
	                double m = 1;
	                while (!isSpaceChar(c)) {
	                    if (c == 'e' || c == 'E')
	                        return res * Math.pow(10, readInt());
	                    if (c < '0' || c > '9')
	                        throw new InputMismatchException();
	                    m /= 10;
	                    res += (c - '0') * m;
	                    c = read();
	                }
	            }
	            return res * sgn;
	        }
	        public long readLong() {
	            int c = read();
	            while (isSpaceChar(c))
	                c = read();
	            int sgn = 1;
	            if (c == '-') {
	                sgn = -1;
	                c = read();
	            }
	            long res = 0;
	            do {
	                if (c < '0' || c > '9')
	                    throw new InputMismatchException();
	                res *= 10;
	                res += c - '0';
	                c = read();
	            } while (!isSpaceChar(c));
	            return res * sgn;
	        }
	        public boolean isSpaceChar(int c)
	        {
	            if (filter != null)
	                return filter.isSpaceChar(c);
	            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	        }
	 
	        public String next()
	        {
	            return readString();
	        }
	 
	        public interface SpaceCharFilter
	        {
	            public boolean isSpaceChar(int ch);
	        }
	    }
	 
	    private static class OutputWriter
	    {
	        private final PrintWriter writer;
	 
	        public OutputWriter(OutputStream outputStream)
	        {
	            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	        }
	 
	        public OutputWriter(Writer writer)
	        {
	            this.writer = new PrintWriter(writer);
	        }
	 
	        public void print(Object... objects)
	        {
	            for (int i = 0; i < objects.length; i++)
	            {
	                if (i != 0)
	                    writer.print(' ');
	                writer.print(objects[i]);
	            }
	        }
	 
	        public void println(Object... objects)
	        {
	            print(objects);
	            writer.println();
	        }
	 
	        public void close()
	        {
	            writer.close();
	        }
	 
	        public void flush()
	        {
	            writer.flush();
	        }
	     }
	}


