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 os, sys, atexit
if sys.version_info[0] < 3:
    range = xrange
    from cStringIO import StringIO as BytesIO

    sys.stdout = BytesIO()
else:
    from io import BytesIO

    sys.stdout = BytesIO()
    _write = sys.stdout.write
    sys.stdout.write = lambda s: _write(s.encode())
atexit.register(lambda: os.write(1, sys.stdout.getvalue()))

input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

from sys import stdout, stdin

out, q = [], int(input())
arr = [int(input()) for _ in range(q)]

for n in arr:
    if n in [1, 2, 3, 5, 7, 11]:
        out.append('-1')
    else:
        ans = 0
        if n & 1:
            ans += 1
            n -= 9

        ans += n // 4
        out.append(str(ans))
stdout.write('\n'.join(out))
