// Pollard’s rho Integer Factoring Algorithm
// Works for  : 10^19
// Complexity : O(n^1/4)

ll pollard_rho(ll n)  //pollard rho implementation
{
    if(n%2==0)
        return 2;
    ll x = rand()%n+1;
    ll c = rand()%n+1;
    ll y = x;
    ll g = 1;

    //fn is f(x) = x*x + c
    while(g==1)
    {
        x = (mulMod(x, x, n) + c)%n;
        y = (mulMod(y, y, n) + c)%n;
        y = (mulMod(y, y, n) + c)%n;
        g = gcd(abs_val(x-y),n);
    }
    return g;
}

map <ll, ll> MAP;
void factorize(ll n)   //f(n) to factorize the number
{
    if(n == 1)
        return;
    if(isPrime(n))      //if n is prime,store it
    {
        MAP[n]++;
        return;
    }
    ll divisor = pollard_rho(n);   //get a divisor of n
    factorize(divisor);
    factorize(n/divisor);
}