← 返回题目列表

Codeforces · 870/C

C. 最大分裂

中文机器翻译题面 查看原题

您会收到几个问题。在第 i 个查询中,您将获得一个正整数 ni。您要将 ni 表示为复合被数的最大可能数量的总和,并打印该最大数量,或者如果没有此类分割,则打印 -1。

大于 1 的整数是合数,如果它不是素数,即它的正因数不等于 1 和整数本身。

输入

第一行包含单个整数 q (1 ≤ q ≤ 105) — 查询数。

q 行如下。第 (i + 1) 行包含单个整数 ni (1 ≤ ni ≤ 109) — 第 i 个查询。

输出

对于每个查询,打印有效拆分为复合被加数的最大可能被加数数量,如果没有此类拆分,则打印 -1。

示例

输入 #1

1
12

输出 #1

3

输入 #2

2
6
8

输出 #2

1
2

输入 #3

3
1
2
3

输出 #3

-1
-1
-1

注意

12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12,但第一次分割具有最大可能的被加数数量。

8 = 4 + 4, 6 不能分解为多个合数被加数。

1、2、3 小于任何合数,因此它们没有有效的分割。