#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int mo=998244353; inline ull read() { static ull x=0,c=getchar() ; for(; c<=47||c>=58; c=getchar()); for(x=0; c>=48&&c<=57; c=getchar()) x=(x<<3)+(x<<1)+(c&15); return x; } ull qp(ull a,ull b) { ull ans=1; while(b) { if(b&1) ans*=a%mo; a*=a%mo; b>>=1; } return ans%mo; } inline bool ch(int a) { int cnt=0; for(int i=1; i*i<=a; i++) if(a%i==0) cnt++; if(cnt==2) return true; return false; } int main() { // freopen("sumdiv.in","r",stdin); // freopen("sumdiv.out","w",stdout); ull t,a,b; t=read(); while(t--) { ull cnt=0,s[0x7fff],t[0x7fff],ans=1; a=read(),b=read(); for(int i=2; i*i<a; i++) { if(a%i==0) { if(ch(i)==true) { cnt++,s[cnt]=i; while(a%i==0) { t[i]++; a/=i; } } } } if(ch(a)) { cout<<((qp(a,b+1)-1)/((a-1)%mo))<<endl; } else { for(ull i=1; i<=cnt; i++) //a=s[cnt],b=t[a] ans*=((qp(s[i],t[s[i]]+1)-1)/((s[i]-1)%mo)); cout<<ans%mo<<endl; } } return 0; } /*for(ull i=1;i*i<=a;i++) if(a%i==0&&i!=1&&i!=a){ if(ch(i)==true) cnt++,s[cnt]=i,t[i]++; else{ for(int j=2;j*j<=i;j++){ if(ch(j)==true){ while(i%j==0){ t[j]++; i/=j; } } } } } */