SPCM - Gopu and function

no tags

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 Vamsi Krishna Avula: 2014-12-29 06:23:25 memoization made no difference :/ as the test cases are just 20, very easy problem, consider making a harder version [Lakshman]: 2014-04-14 17:22:42 @ivar try this 2 467841156412 478561115648 output:: 18 11 Mitch Schwartz: 2014-01-14 19:47:38 Note that we are counting distinct prime divisors, based on the example and also the fact that f(4) would be undefined otherwise. :p Last edit: 2014-01-14 13:53:50