HDU-6265 Master of Phi

$Description$
$\sum_{d|n}\varphi(d) \cdot \frac{n}{d}$

$Solution$
$\sum_{d|n}\varphi(d) \cdot \frac{n}{d} \\ =n\cdot \prod_{p^a||n}\sum_{k=0}^{a}\frac{\varphi (p^k)}{p^k} \\ =n\cdot \prod_{p^a||n}(1+\sum_{k=1}^{a}\frac{(p^k-p^{k-1})}{p^k}) \\ =\prod_{p^a||n}p^{a-1}\cdot(p\cdot a+p-a)$

$Code$

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll quick(ll p,ll a)
{
    ll ans=1;
    while(a)
    {
        if(a&1)
            ans=ans*p%mod;
        a>>=1;
        p=p*p%mod;
    }
    return ans%mod;
}
int main()
{
    ll p[25],q[25];
    ll t;cin>>t;
    while(t--)
    {
        ll m;
        cin>>m;
        for(ll i=1;i<=m;i++)
        {
            scanf("%lld%lld",p+i,q+i);
        }
        ll ans=1;
        for(ll i=1;i<=m;i++)
        {
            ll mi=quick(p[i],q[i]-1);
            ans=ans*(p[i]*q[i]%mod+p[i]-q[i]+mod)%mod*mi%mod;
        }
        cout<<(ans+mod)%mod<<endl;
    }
}