#include<bits/stdc++.h> #define N 10000000 #define ll long long #define mod 998244353 using namespace std; inline ll read(){ ll x(0),f(1);char c(getchar()); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return x*f; } ll fpow(ll a,ll b){ if(!b) return 1; ll t(fpow(a,b>>1)); if(b&1) return t*t%mod*a%mod; return t*t%mod; } int T,a,b,tot; vector <ll> p,cnt; ll prime[N],vis[N],ans; int main(){ // freopen("sumdiv.in","r",stdin); // freopen("sumdiv.out","w",stdout); for(int i(2);i<=N;++i){ if(!vis[i]) prime[++tot]=i; for(int j(1);i*prime[j]<=N&&j<=tot;++j){ vis[i*prime[j]]=1; if(!(i%prime[j])) break; } } T=read(); while(T--){ p.clear();cnt.clear();ans=1; a=read();b=read(); for(int i(1),res;prime[i]*prime[i]<=a&&(a^1);++i) if(!(a%prime[i])){ p.push_back(prime[i]); res=0;while(!(a%prime[i])) {a/=prime[i];++res;} cnt.push_back(res); } if(a^1){ p.push_back(a); cnt.push_back(1); } for(int i(0);i<p.size();++i){ if(p[i]%mod==1) ans=ans*(cnt[i]*b+1)%mod; else ans=ans*(fpow(p[i]%mod,cnt[i]*b+1)-1)%mod*fpow((p[i]-1)%mod,mod-2)%mod; } printf("%lld\n",(ans%mod+mod)%mod); } return 0; }