Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Maximum splitting

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given several queries. In the *i*-th query you are given a single positive integer *n*_{i}. You are to represent *n*_{i} 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* ≤ 10^{5}) — the number of queries.

*q* lines follow. The (*i* + 1)-th line contains single integer *n*_{i} (1 ≤ *n*_{i} ≤ 10^{9}) — 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.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/20/2019 19:36:43 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|