A Nightmare Quiz
Tag(s):

## Easy-Medium, Math, Number Theory, Sieve

Problem
Editorial
Analytics

Omar is an intelligent guy who loves programming very much especially problem solving.

After an exhausting university day he returned to his house and started to solve programming problems. But he was very tired so he felt asleep.

Unfortunately it was a nightmare, to be specific it was a nightmare quiz where monsters gave him questions and he had to answer them correctly to avoid their anger.

He was asked to count the number of non prime pairs which form a given number N.

Non prime pair which form N is 2 different non prime numbers and product of this numbers has to be equal N. For example, $N = 24$, there are $2$ good pairs (non prime pairs that form N) $(4 , 6)$, $(1 , 24)$ but $(2 , 12)$ , $(3 , 8)$ are not good.

Note: for any 2 numbers a and b pair $(a , b)$ = pair $(b , a)$.

Unfortunately, monsters have added another condition which state that if the number is a special number, Omar should output -1 otherwise he should count the number of non prime pairs. Number is called special if it can be represented as a product of three prime numbers. For example: 12 is a special number because $12 = 2 \cdot 2 \cdot 3$.

Input:

In the first line given an integer $T$, $1 \le T \le 10 ^ 6$, representing the number of test cases. Each of the next T contains an integer $N$, $1 \le N \le 10 ^ 6$.

Output:

For every test case output -1 if N is a special number, otherwise print the number of non prime pairs which forms N.

SAMPLE INPUT
2
24
12

SAMPLE OUTPUT
2
-1

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

## CODE EDITOR

Initializing Code Editor...