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.*;
import java.util.*;
public class Asd {
static PrintWriter w=new PrintWriter(System.out);
static FastScanner s=new FastScanner();

	public static void main(String[] args) {
		
		int t=s.nextInt();
              //  int t=1;
		while(t-->0)
                {
		    solve();
		}
	       w.close();
        }
        /* Function to print all the permutations of the string
        static String swap(String str, int i, int j)
        {
        char ch;
        char[] array = str.toCharArray();
        ch = array[i];
        array[i] = array[j];
        array[j] = ch;
        return String.valueOf(array);
       }
    
      static void permute(String str,int low,int high)
    {
        if(low == high)
            list.add(Long.parseLong(str));
 
        int i;
        for(i = low; i<=high; i++){
            str = swap(str,low,i);
            permute(str, low+1,high);
            str = swap(str,low,i);
        }
    }
        use  permute(str2,0,str2.length()-1); to perform combinations
        */
           public static void solve()
        {
          int n=s.nextInt();
          int arr[]=new int[16];
          for(int i=1;i<=15;i++)
          {
              if(i==1||i==2||i==3||i==5||i==7||i==11||i==11)
                  arr[i]=-1;
              if(i%4==0)
                  arr[i]=i/4;
              if(i==10||i==13)
                  arr[i]=2;
              if(i==14)
                  arr[i]=3;
              if(i==6||i==9)
                  arr[i]=1;
              
          }
          arr[15]=2;
          if(n<=15)
          {
              w.println(arr[n]);return;
          }
          if(n%4==1)
          {
              w.println(1+(n-9)/4);return;
          }
          if(n%4==2)
          {
              w.println(1+(n-6)/4);return;
          }
          if(n%4==3)
              {
              w.println(2+(n-15)/4);return;
          }
          else
              {
              w.println(n/4);return;
          }
        }
           
        static int noofdivisors(int n)
        {
            //it counts no of divisors of every number upto number n
            
            int arr[]=new int[n+1];
              for(int i=1;i<=(n);i++)
			for(int j=i;j<=(n);j=j+i)
				arr[j]++;
             return arr[999999];
        }
           
        
       
        static char[] reverse(char arr[])
        {
            char[] b = new char[arr.length]; 
        int j = arr.length; 
        for (int i = 0; i < arr.length; i++) { 
            b[j - 1] = arr[i]; 
            j = j - 1; 
        }
        return b;
        }
        
        
	static long factorial(int n)
        {
            long su=1;
            for(int i=1;i<=n;i++)
                su*=(long)i;
            return su;
        }
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		public String next() {
			while (!st.hasMoreElements())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int[] readArray(int n) {
			int[] a=new int[n]; 
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		
		int nextInt () {
			return Integer.parseInt(next());
		}
                long nextLong () {
			return Long.parseLong(next());
		}
                double nextDouble () {
			return Double.parseDouble(next());
		}
	}

}
