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\).

Omar needs your help!

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.