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.util.*;

public class CodeForces
{
    static long count(long n) 
    { 
        // 4 is the smallest composite number 
        if (n < 4) 
            return -1; 
      
        // stores the remainder when n is divided 
        // by 4 
        long rem = n % 4; 
      
        // if remainder is 0, then it is perfectly  
        // divisible by 4. 
        if (rem == 0) 
            return n / 4; 
      
        // if the remainder is 1 
        if (rem == 1) { 
      
            // If the number is less then 9, that 
            // is 5, then it cannot be expressed as  
            // 4 is the only composite number less  
            // than 5 
            if (n < 9) 
                return -1; 
      
            // If the number is greater then 8, and  
            // has a remainder of 1, then express n 
            // as n-9 a and it is perfectly divisible  
            // by 4 and for 9, count 1. 
            return (n - 9) / 4 + 1; 
        } 
      
          
        // When remainder is 2, just subtract 6 from n,  
        // so that n is perfectly divisible by 4 and 
        // count 1 for 6 which is subtracted. 
        if (rem == 2) 
            return (n - 6) / 4 + 1; 
      
      
        // if the number is 7, 11 which cannot be  
        // expressed as sum of any composite numbers 
        if (rem == 3)  
        { 
            if (n < 15) 
                return -1; 
      
            // when the remainder is 3, then subtract 
            // 15 from it and n becomes perfectly  
            // divisible by 4 and we add 2 for 9 and 6, 
            // which is getting subtracted to make n  
            // perfectly divisible by 4. 
            return (n - 15) / 4 + 2; 
        } 
        return 0; 
    } 

    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int u=0;u<t;u++)
        {
            long n=sc.nextLong();
            System.out.println(count(n));
        }
    }
}