#include <bits/stdc++.h> using namespace std; const int MXV = 3163; const int DVS = 998244353; int T, A, B, pms[MXV + 5], inv[MXV + 5], pid, ans; bitset<MXV + 5> ivl; int read() { int x(0); char c(getchar()); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x; } void write(int x) { if (x >= 10) write(x / 10); putchar((x % 10) | 48); } void exgcd(int a, int b, int &x, int &y) { if (!b) x = 1, y = 0; else exgcd(b, a % b, y, x), y -= a / b * x; } int pw(int b, long long p) { int ans(1); while (p) { if (p & 1) ans = ans * 1LL * b % DVS; b = b * 1LL * b % DVS; p >>= 1; } return ans; } int main() { // freopen("sumdiv.in", "r", stdin); // freopen("sumdiv.out", "w", stdout); ivl[0] = ivl[1] = true; for (int i(2); i <= MXV; ++i) { if (!ivl[i]) { int t(0); exgcd(i - 1, DVS, inv[pid], t); inv[pid] = (inv[pid] % DVS + DVS) % DVS; pms[pid++] = i; } for (int j(0), x(0), f(1); f && j != pid && (x = i * pms[j]) <= MXV; ++j) { ivl[x] = true; if (!(i % pms[j])) { f = 0; } } } T = read(); while (T--) { A = read(); B = read(); ans = 1; for (int i(0); i != pid && pms[i] * pms[i] <= A; ++i) { int k(0); while (A % pms[i] == 0) ++k, A /= pms[i]; ans = ans * 1LL * ((pw(pms[i], k * 1LL * B + 1) + DVS - 1) % DVS) % DVS * 1LL * inv[i] % DVS; } if (A != 1) { int x(0), y(0); exgcd(A - 1, DVS, x, y); x = (x % DVS + DVS) % DVS; ans = ans * 1LL * ((pw(A, B + 1) + DVS - 1) % DVS) % DVS * 1LL * x % DVS; } write(ans); putchar(10); } // cout << clock() / 1000.0 << endl; return 0; }