59 lines
1.1 KiB
Java
59 lines
1.1 KiB
Java
package chelper;
|
||
|
||
import java.util.Arrays;
|
||
|
||
import io.InputReader;
|
||
import io.OutputWriter;
|
||
import misc.SimpleSavingChelperSolution;
|
||
|
||
|
||
public class С extends SimpleSavingChelperSolution {
|
||
|
||
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
||
wrapSolve(testNumber, in, out);
|
||
}
|
||
|
||
@Override
|
||
public void solve(int testNumber) {
|
||
int q = in.nextInt();
|
||
|
||
int M = 1000;
|
||
boolean[] primes = new boolean[M];
|
||
Arrays.fill(primes, true);
|
||
primes[0] = false;
|
||
primes[1] = true;
|
||
for (int i = 2; i < M; i++) {
|
||
if (!primes[i]) {
|
||
continue;
|
||
}
|
||
|
||
for (int j = i * 2; j < M; j += i) {
|
||
primes[j] = false;
|
||
}
|
||
}
|
||
|
||
int[] dp = new int[M];
|
||
Arrays.fill(dp, -1);
|
||
|
||
for (int i = 1; i < M; i++) {
|
||
if (!primes[i]) {
|
||
dp[i] = 1;
|
||
}
|
||
for (int j = 1; j < i; j++) {
|
||
if (!primes[j] && !primes[i - j]) {
|
||
dp[i] = Math.max(dp[i], dp[j] + dp[i - j]);
|
||
}
|
||
}
|
||
}
|
||
|
||
for (int i = 0; i < q; i++) {
|
||
int n = in.nextInt();
|
||
if (n < M) {
|
||
out.println(dp[n]);
|
||
} else {
|
||
out.println(n / 4 - n % 2);
|
||
}
|
||
}
|
||
}
|
||
}
|