#include <bits/stdc++.h> using namespace std; const int Mod=998244353; const int Maxn=1e7+5; typedef long long ll; int T,a,b,cnt; struct Node { int n,m; } num[500005]; int p,prime[500005]; bool ma[Maxn]; inline int read() { int x=0; char c=getchar(); for(; c<'0' || c>'9'; c=getchar()); for(; c<='9' && c>='0'; c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x; } inline ll Pow(int x,int k) { ll ans=1; while(k) { if(k&1) ans=ans*x%Mod; x=x*x%Mod; k>>=1; } return ans; } inline void Init() { for(int i=2; i<=Maxn; i++) { if(!ma[i]) prime[++p]=i; for(int j=1; j<=p && i*prime[j]<=Maxn; j++) { ma[i*prime[j]]=1; if(i%prime[j]==0) break; } } } inline ll Calc(int c,int n) { if(c==1) return 1; return (((Pow(c,n+1)-c)/(c-1))%Mod)%Mod; } int main() { T=read(); Init(); while(T--) { ll sum=1; a=read(),b=read(); if(a<=12 && b<=12) { a=Pow(a,b); for(int i=1; i*i<=a; i++) { if(a%i==0) { sum=(sum+i)%Mod; if((a/i)!=i) sum=(sum+a/i)%Mod; } } cout<<sum%Mod<<'\n'; return 0; } //cout<<Calc(3,2)<<'\n'; for(int i=1; i<=p; i++) { if(a%prime[i]==0) { int rec=0; while(a%prime[i]==0) { a/=prime[i]; rec++; } num[++cnt].n=prime[i],num[cnt].m=rec; //cout<<prime[i]<<' '<<rec<<'\n'; } } for(int i=1; i<=cnt; i++) { ll now=0; for(int j=1; j*j<=num[i].n; j++) if(num[i].n%j==0) { now=(now+Calc(j,num[i].m*b))%Mod; if((num[i].n/j)!=j) now=(now+Calc(num[i].n/j,num[i].m*b)%Mod); } sum=sum*now%Mod; } cout<<sum%Mod<<'\n'; } return 0; }