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 math;
from math import log2,sqrt;
from bisect import bisect_left,bisect_right
import bisect;
import sys;
from sys import stdin,stdout
import os
sys.setrecursionlimit(pow(10,6))
import collections
from collections import defaultdict
from statistics import median
# input=stdin.readline
# print=stdout.write
from queue import Queue
inf = float("inf")
maxa=pow(10,5)
prime=[True for i in range(maxa+1)]
def sieve(n=maxa):
    p=2;
    while(p*p<=n):
        if prime[p]:
            for i in range(p*p,n+1,p):
                prime[i]=False;

        p+=1
sieve(maxa)

composite=[]
least=1000
for i in range(2,least+1):
    if not prime[i]:
        composite.append(i)
dp=[-inf]*least
dp[0]=0
for i in range(len(dp)):

    for j in range(len(composite)):
        if composite[j]<=i:
            dp[i]=max(dp[i],dp[i-composite[j]]+1)
        else:
            break;
t=int(input())
def fun(n):
    left=(n-least)%4;
    n_copy=n;
    n=least+left-4;
    dec=n_copy-n;
    return dec//4,n
for i in range(t):
    n=int(input())
    pre_process=0
    if n>=least:
        pre_process,n = fun(n)
    if dp[n]==-inf:
        dp[n]=-1

    print(dp[n]+pre_process)









