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

hide comments
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

Added by:praveen123
Date:2013-12-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge