int bigmod(int a , int p , int mod) /// (a ^ p) % mod
{
    if(p == 0) return 1;
    int ans = bigmod(a , p/2 , mod); /// p = 9 , p/2 = 4
    ans = 1LL * ans * ans % mod; /// ans = a ^ 8
    if(p % 2 == 1){
        ans = 1LL * ans * a % mod;
    }
    return ans;
}

/// factor = 2
/// multiple: 2 , 4, 6 , 8 , 10 , 12 , 14 , ...

vector < int > factors[N];

void factorize(int n) /// factorize from 1 to n
{
    for(int factor = 1 ; factor <= n ; factor++){ /// O(n)
        for(int multiple = factor ; multiple <= n; multiple += factor){
            factors[multiple].push_back(factor);
        }
    }
}



vector < int > sieve(int n)
{
    vector < int > prime;
    vector < bool > vis(n+1);
    for(int i = 3 ; 1LL*i*i <= n; i += 2){ /// O(sqrt(n))
        if(vis[i] == 0){ /// 'i' is a prime /// i = 11
            for(int j = i*i ; j <= n ; j += i+i){ /// j = 22
                vis[j] = 1;
            }
        }
    }
    prime.push_back(2);
    for(int i = 3 ; i <= n ; i += 2){
        if(vis[i] == 0) prime.push_back(i);
    }
    return prime;
}


vector < pair < LL , int > > PrimeFactorize(LL n)
{
    vector < pair < LL , int > > ans;
    vector < int > prime = sieve(1e6);
    for(int p:prime){
        if(n % p == 0){
            int cnt = 0;
            while(n % p == 0){
                n /= p;
                cnt++;
            }
            ans.push_back({p  , cnt});
        }
    }
    if(n > 1){
        ans.push_back({n , 1});
    }
    return ans;
}