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.
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
Shining through the city with a little funk and soul
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class A
   {
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         int[] dp = new int[41];
         Arrays.fill(dp, -1);
         dp[4] = 1;
         for(int i=5; i < 41; i++)
         {
            if(!isPrime(i))
               dp[i] = 1;
            for(int v=4; v < 41; v++)
               if(!isPrime(v) && i-v > 0 && dp[i-v] != -1)
                  dp[i] = Math.max(dp[i], dp[i-v]+1);
         }
         while(T-->0)
         {
            int N = Integer.parseInt(infile.readLine());
            if(N <= 40)
               sb.append(dp[N]+"\n");
            else
            {
               long low = 1;
               long high = N;
               while(low != high)
               {
                  long mid = (low+high)/2;
                  if(N-4*mid >= 40)
                     low = mid+1;
                  else
                     high = mid;
               }
               int res = (int)low;
               res += dp[N-4*(int)low];
               if(dp[N-4*(int)low] == -1)
                  res = -1;
               sb.append(res+"\n");
            }
         }
         System.out.print(sb);
      }
      public static boolean isPrime(long n) 
      {
          if(n < 2) return false;
          if(n == 2 || n == 3) return true;
          if(n%2 == 0 || n%3 == 0) return false;
          long sqrtN = (long)Math.sqrt(n)+1;
          for(long i = 6L; i <= sqrtN; i += 6) {
              if(n%(i-1) == 0 || n%(i+1) == 0) return false;
          }
          return true;
      }
   }