CF870C.Maximum splitting

You 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.

你将收到若干查询。在第 $i$ 个查询中，你会得到一个正整数 $n_i$。你需要将 $n_i$ 表示为尽可能多的合数之和，并输出这个最大数量；如果不存在这样的拆分，则输出 $-1$。

大于 1 的整数称为合数，当且仅当它不是质数，即它存在不等于 1 和其自身的正因数。

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 n__i (1 ≤ n__i ≤ 109) — the i-th query.

第一行包含一个整数 $q$（$1 \le q \le 10^5$）—— 查询的个数。

接下来有 $q$ 行。第 $(i + 1)$ 行包含一个整数 $n_i$（$1 \le n_i \le 10^9$）—— 第 $i$ 个查询。

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.

对于每个查询，输出在合法的合数拆分中最多可能的加数个数；若不存在这样的拆分，则输出 $-1$。

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.

12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12，但第一种拆分方式具有最多可能的加数个数。

8 = 4 + 4，而 6 无法被拆分为若干个合数之和。

1、2、3 均小于任意合数，因此它们均不存在有效的拆分。