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.BufferedReader;

import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * problemaA
 */
public class problemaA {

    static boolean prime(int n) {
        if (n < 2) return false;
        for (int x = 2; x*x <= n; x++) {
            if (n%x == 0) return false;
        }
        return true;
    }
        
    static int MAX_MIN_NUMBER = 15;
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int q = Integer.parseInt(bf.readLine());
        int[] arr = new int[q];
        for(int i = 0; i < q; i++){
            arr[i] = Integer.parseInt(bf.readLine());
        }

        List<Integer> dp = new ArrayList<>();
        Set<Integer> primes = new HashSet<>();
        primes.add(1);
        for(int i = 2; i <= MAX_MIN_NUMBER; i++){
            if(!prime(i)) {
                dp.add(i);
            }
            else primes.add(i);
        }

        int[] saves = savePrimosMenores15(dp);
        
        for(int x : arr){
           System.out.println(solve(x, saves));
        }
    }

    static int[] savePrimosMenores15(List<Integer> dp){
        int[] reach = new int[16];
        Arrays.fill(reach, -1);
        reach[0] = 0;
        for(int i = 1; i <= MAX_MIN_NUMBER; i++){

            for(int x : dp){
                if(i < x) break;
                if(i-x >= 0 && reach[i-x] >= 0) 
                    reach[i] = Math.max(reach[i], reach[i-x]+ 1);
            }
        }

        return reach;  
    }

    static int solve(int n, int[] saves){
        if(n <= 15) return  saves[n];
        
        int k = (int) Math.ceil((double)((double)n-15)/(double)4);
        return saves[n-(4*k)]+k;
    }
}

// 