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 Solution{  
      
      static int mod=1000000007;


     static int solve(int n){
                 int ans=-1;
                 int m = n%4;
                 if(m==0)
                   ans = n/4;
                 else if(m==1){
                     n =n-9;
                     if(n>=0)
                       ans=(n/4)+1;
                 }
               else if(m==2){
                      n = n-6;
                      if(n>=0)
                        ans=(n/4)+1;
                 }
              else if(m==3){
                      n = n-15;
                      if(n>=0)
                         ans=(n/4)+2;
               }
                    return(ans);
             }
      public static void main(String[] args){ 
                  
                int t = intt();
              for(int ss=1;ss<=t;ss++){
                        int n = intt();
                        out.println(solve(n));
                 }
                  

             out.flush();
    } 

         static FastReader sc=new FastReader();
         static PrintWriter out = new PrintWriter(System.out);
            static int intt(){
                       int x = sc.nextInt();
                       return(x);
                }
               static long longg(){
                          long x = sc.nextLong();
                           return(x);
                }
               static double doublee(){
                          double t = sc.nextDouble();
                           return(t);
                }
              static String str(){
                       String s = sc.next();
                         return(s);
                }
              static String strln(){

                        String s = sc.nextLine();
                           return(s);
              }
              static long pow(long a,long b){
                       long ans=1;
                      while(b>0){
                          if(b%2==1)
                              ans=(ans*a);
                              a=(a*a)%mod;
                              b=b/2;
                      }
                    return(ans);
                }
           
            static long LCM(long a,long b){
                         return ((a*b)/GCD(a,b));
               }
               static long GCD(long a,long b){
                          
                           if(b%a==0)
                              return(a);
                              return(GCD(b%a,a));
              }

                static long abs(long x,long y)
                   { return(Math.abs(x-y));}

              static long min(long x,long y){
                     return(Math.min(x,y));
                 }

              static long max(long a,long b){
                        return Math.max(a,b);
                  } 

              static long Fermat(long a,long p){
                           long b = p-2,ans=1;
                            while(b>0){
                                 if(b%2==1)
                                      ans=(ans*a)%p;
                                       a=(a*a)%p;
                                       b=b/2;
                              }
                           return(ans);
                   }
              static void Fact(long a[],long m){
                              a[0]=1;
                           for(int i=1;i<a.length;i++)
                                   a[i]=(i*a[i-1])%m;

                      }
              static void Fact_Inv(long a[],long F[],long m){

                                 int n =a.length;
                                     a[n-1]=Fermat(F[n-1],m);
                                 for(int i=n-2;i>=0;i--)
                                        a[i]=((i+1)*a[i+1])%m;
                        }
               /*static  long d, x, y;
              static void extendedEuclid(long A, long B) {
                            if(B == 0) {
                                  d = A;
                                  x = 1;
                                  y = 0;
                              }
                           else {
                                extendedEuclid(B, A%B);
                                 long temp = x;
                                  x = y;
                                 y = temp - (A/B)*y;
                            }
                     } */
                 /*static class pair implements Comparable<pair>{
                       int x,y;
                      pair(int a,int b){
                             x=a;
                             y=b;
                       }
                     public int compareTo(pair p1)
                           { return((p1.x-p1.y)-(this.x-this.y));}
          
                   public boolean equals(Object obj) {
                         if (this == obj)
                                return true;
                        if (obj == null)
                                return false;
                        if (getClass() != obj.getClass())
                                return false;
                         pair other = (pair) obj;
                          if (x != other.x)
                                  return false;
                          if (y != other.y)
                                  return false;
                            return true;
                      }
                      @Override
                 public int hashCode() {
                      return(x-y);
                   } 
          }   */
   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; 
        } 
    } 
}