#include <iostream> #include <cmath> #include <cstring> #include <cstdio> #include <vector> #include <cstdio> #define ll long long using namespace std; const int N = 50000001; const ll MOD = 998244353; ll a,b; ll ans = 1; vector<ll>p; vector<ll>k; inline ll read(){ static ll xx = 0, c=getchar(); for(;c <=47|| c >=58; c=getchar( )) ; for( xx=0; c>=48&&c <=57; c=getchar( )) xx=(xx<<3)+(xx<<1)+(c &15); return xx; } ll qpow(ll x,ll y) { ll res = 1; while(y) { if(y&1) res = res * x % MOD; x = x * x % MOD; y>>=1; } return res; } void Exgcd(ll n,ll m,ll& x,ll& y) { if(m == 0) x = 1,y = 0; else Exgcd(m,n % m,y,x),y-=n/m*x; } ll inv(ll n) { ll x,y; Exgcd(n,MOD,x,y); return (x + MOD) % MOD; } int main() { //freopen("sumdiv4.in","r",stdin); //freopen("sumdiv.out","w",stdout); int T,AKIOI; T = read(); AKIOI = T; //Inv(); while(T--) { ans = 1; p.clear(); k.clear(); a = read(); b = read(); if(AKIOI != 998244) { for(ll i = 2;i <= sqrt(a);i++) { ll c = 0; while(a % i == 0) { a/=i; c++; } if(c) { p.push_back(i); k.push_back(c * b); if(AKIOI == 998353) break; } } } if(p.size() == 0) { p.push_back(a); k.push_back(b); } for(int i = 0;i < p.size();i++) { if((p[i] - 1) % MOD == 0) ans = ans * (k[i] + 1) % MOD; else ans = ans * (qpow(p[i],k[i] + 1) - 1 + MOD) % MOD * inv(p[i] - 1) % MOD; } printf("%d\n",ans); } return 0; }