For Turbo C++ Users : Read the following document before attempting the question :

Problem Description
Hank Pym is an aspiring student at IIITD. He has almost completed his work on Ultron, the ultimate artificial intelligence. However, one thing remains. He feels that Ultron should have a fail-safe code which can be used to switch him off (just in case Ultron decides to wipe out our race). So, he encodes the number and feeds it into Ultron. Hank shares the number with the rest of the Avengers and the way to decrypt it:

Divide the encrypted number ‘N’ by its biggest prime divisor. Now, divide the resultant number by its biggest prime divisor and continue the process (i.e., recursively) until the resultant number doesn’t have any prime divisors. The decrypted code is the number of times you have to do this process.

Hank wants you to decrypt the number for him, so that he may store it somewhere safe (maybe inside one of the books at the IIITD library).Can you help Hank?

Input
First line contains ‘T’, the number of test cases.
Each test case is given on a new line, which consists of a number the encrypted number 'N'.

Output
For each test case, print the decrypted number.

Constraints
Should contain all the constraints on the input data that you may have. Format it like:

1 ≤ T ≤ 100
1 ≤ N ≤ 10^9

Example
Input:
4
2
9
100
17

Output:
1
2
4
1

Explanation

For the first test case, 2 has no prime divisors apart from itself. So, the answer is 1.
For the second test case, 9 has 3 as the only prime divisor. Dividing it by 3, we get 3.Dividing 3 by itself, we get 1, which has no prime divisors. So, the answer is 2.
For the third test case, the largest prime divisor is 5. Dividing, we get 20.The largest prime factor of 20 is 5. So, dividing by 5, we get 4. The largest prime factor of 4 is 2. Dividing, we get 2. Again dividing 2 by 2, we stop at 1.So, we did the division 4 times. Hence, the answer is 4.
The fourth test case is similar to the first test case.

见题面

见题面