Sanjeev is an intelligent boy who loves problem solving. After an exhausting university day, he returned to his house and started solving problems. Soon he got tired and fell 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 are 2 different non prime numbers and product of this numbers has to be equal N. For example, If N=24 then 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 states 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⋅2⋅3.
Sanjeev is our Bro , can you help him ?
INPUT:
First line contains T , the number of test cases . Each test case contains a number N in a new line
CONSTRAINTS:
1 ≤ T≤106
1 ≤ N ≤ 106
OUTPUT:
No. of Good pairs that form N in a new line .
