链接：Master of Phi

题意：求$\sum_{d\mid n} \phi(d)* \frac{n}{d}$，其中$n=\prod_{i=1}^{m}{p_{i}}^{q_{i}}$

思路：设$f(n)=\sum_{d\mid n} \phi(d)* \frac{n}{d}$，显然$f(n)$是积性函数

$f(n)=f({p_1}^{c_1}*{p_2}^{c_2}*\cdots * {p_m}^{c_m})=f({p_1}^{c_1})*f({p_2}^{c_2})*\cdots *f({p_m}^{c_m})$

由f(n)定义得

$$f(p^c)=\phi(1)*n+\phi(p)*\frac{n}{p}+\phi(p^2)*\frac{n}{p^2}+\cdots +\phi(p^c)*\frac{n}{p^c}$$

$$f(p^c)=n+(p-1)*\frac{n}{p}+(p^2-p)*\frac{n}{p^2}+\cdots +(p^c-p^{c-1})*\frac{n}{p^c}$$

$$f(p^c)=n*(1+c*\frac{p-1}{p})=p*c+c*(p-1)*p^{c-1}$$

其中$n=p^c$

即

$$f(p^c)=p*c+c*(p-1)*p^{c-1}$$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

const int N = 30;
const ll mod = 998244353;

int T, m;

ll power(ll a, ll n)
{
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &m);
        ll res = 1;
        for (int i = 1; i <= m; i++) {
            ll p, c;
            scanf("%lld%lld", &p, &c);
            ll a = power(p, c), b = c * (p - 1) % mod * power(p, c - 1) % mod;
            res = res * ((a + b) % mod) % mod;
        }
        printf("%lld\n", res);
    }
    return 0;
}