F. Phoebe And Magic Marbles

5

1 votes
Sieve, Medium
Problem

Phoebe found a magic marble in a soda can. The magic marble has a specific number written on it. She thinks that this magic marble was not in her fate and so she has decided to destroy the marble. She has a special type of liquid which can help her to destroy the marble.

She can use one drop of liquid and decompose the marble into different magic marbles having its extremely proper divisors. These new marbles can again be decomposed by repeating the process. If the magic marble has a number which has no extremely proper divisors, then that magic marble gets destroyed on its own.

She knows destroying the marble in this way will use a lot of liquid and so she wants your help to count the number of drops of liquid required to totally destroy the magic marble.

Extremely Proper Divisors:- Extremely Proper divisors of a number are divisors of the number except one and itself. For e.g. extremely proper divisors of 8 are 4 & 2.

Note:- Consider only the distinct divisors. For e.g. magic marble 25 decomposes into only one magic marble 5.

See the sample case for better understanding.


Input format:

First line contains an integer q denoting the number of queries

Next q lines contains an integer n denoting the number written on Phoebe's magic marble


Output format:

For each query, print the total number of drops required for total destruction of marble.


Constraints:

1 <= q <= 1000000

1 <= n <= 1000000

Sample Input
2
3
12
Sample Output
1
8
Time Limit: 2.5
Memory Limit: 256
Source Limit:
Explanation

In first query, we can use one drop and as 3 has no extremely proper divisor it will get destroyed.

In second query,
We can use one drop on 12 which will form 4 marbles{2, 3, 4, 6}. ---> Drops used = 1
We can use two drops to destroy 2 and 3(as they don't have extremely proper divisors). ---> Drops used = 2
We can use one drop and decompose 4 into 2, which can be destroyed using one drop. ---> Drops used = 2
We can use one drop and decompose 6 into 2 and 3, which can be totally destroyed using two drops. ---> Drops used = 3
Hence, total drops used = 1 + 2 + 2 + 3 = 8.

Editor Image

?