//sumdiv #include <bits/stdc++.h> #ifndef MODINT_HPP #define MODINT_HPP template <const int mod> struct modint; template <const int mod> modint<mod> pow(modint<mod> a, int x) { modint<mod> ans(1); while (x) { if (x & 1) ans *= a; x >>= 1; a *= a; } return ans; } template <const int mod> modint<mod> inv(modint<mod> x) { return pow(x, mod - 2); } // type=int, mod template <const int mod> struct modint { private: int v; #define mod_turn(x) ((x) %= (mod), ((x) < 0) ? ((x) += mod) : 0, (x)) #define ll long long public: modint() = default; modint(int _v) : v(_v) { mod_turn(v); } operator int() const { return v; } int& val() { return v; } modint operator+(const modint& x) const { int p(v + x.v); mod_turn(p); return modint(p); } modint& operator+=(const modint& x) { return v += x.v, mod_turn(v), *this; } modint operator-(const modint& x) const { int p(v - x.v); mod_turn(p); return modint(p); } modint& operator-=(const modint& x) { return v -= x.v, mod_turn(v), *this; } modint operator*(const modint& x) const { ll p(1ll * v * x.v); mod_turn(p); return modint(int(p)); } modint& operator*=(const modint& x) { return *this = *this * x, *this; } modint operator/(const modint& x) const { return *this * inv(x); } modint& operator/=(const modint& x) { return *this = *this * inv(x), *this; } }; #endif using namespace std; typedef modint<998244353> mint; int a, b; mint sum(int x, int y) { y *= b; if (x % 998244353 == 1) { return y + 1; } return (pow(mint(x), y + 1) - mint(1)) / mint(x - 1); } vector<pair<int, int> > yz; int main() { // freopen("sumdiv5.in", "r", stdin); // freopen("sumdiv.out", "w", stdout); int t; scanf("%d", &t); while (t--) { scanf("%d%d", &a, &b); yz.clear(); for (int i = 2; i * i <= a; i++) { if (a % i == 0) { int tt = 0; while (a % i == 0) { a /= i; tt++; } yz.push_back(make_pair(i, tt)); } } if (a != 1) { yz.push_back(make_pair(a, 1)); } mint ans = 1; for (vector<pair<int, int> >::iterator it = yz.begin(); it != yz.end(); ++it) { ans *= sum(it->first, it->second); } printf("%d\n", ans.val()); } return 0; }