Vanshika has a lot of chocolates.She needs to distribute them among her classmates such that maximum number of her peers will get it and she doesnt get beaten up by her friends.
Find the maximum no.of partitions she can make such that each of her peers gets composite number of chocolates because her friends consider composite numbers to be lucky.
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 partitions in a valid splitting to composite number of chocolates, or -1, if there are no such splittings.
12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, but the first splitting has the maximum possible number of summands (they are composite)
