All submissions for this problem are available.Some natural numbers can be represented as an addition of two or more prime numbers (need not be distinct). For a given integer $N$, find minimum number of such **addition operations** required to represent $N$ as an addition of two or more prime numbers if possible otherwise print $-1$ instead. ###Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first and only line of each test case contains single integer $N$. ###Output For each test case, print a single line denoting the answer. ###Constraints - $1 \leq T \leq 10^6$ - $1 \leq N \leq 10^6$ ###Sample Input 4 2 4 11 33 ###Sample Output -1 1 2 1 ###Explanation $2$ cannot be represented as sum of two or more prime numbers. We can represent $4$ as $2+2$, therefore only $1$ addition operation is required. We can represent $11$ as $2+2+7$, therefore $2$ addition operations are required. We can represent $33$ as sum of primes in many ways. For example, $2+2+29$ or $2+31$, but minimum number of addition operations required is $1$.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions