Once Gopu was reading a maths problem which had a weird looking function f as follows.

                {
                         1, if n is a prime number.
f(n)  =                f (sum of prime divisors of n) + number of distinct prime divisors of n,  otherwise.
                }

Compute f (n) for a given value of n. 

Input

First line contains T : number of test cases. (1 ≤ T ≤ 20)

For each test case, there is a single line containing integer n. (2 ≤ n ≤ 10¹²).

Output

For each test case, output value of f (n) in a single line.

Example

Input:
6
2
3
4
5
20
123456 
Output:
1
1
2
1
3
6