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^12).

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