CF870C.Maximum splitting

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

输入格式

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.

输出格式

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
```
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$ , 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.

首页