您会收到几个问题。在第 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 小于任何合数,因此它们没有有效的分割。