#include <bits/stdc++.h> using namespace std; #define mod 998244353 inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } template<typename T> inline void write(T X){ if(X<0){ putchar('-');X=~(X-1);} int s[50],top=0; while(X){ s[++top]=X%10;X/=10;} if (!top) s[++top]=0; while(top) putchar(s[top--]+'0'); putchar('\n'); return; } int a,b,T,cnt,res,ans,k[30],p[30]; inline int QPow(int x,int y){ int ans=1; while(y){ if(y&1)ans*=1ll*x%mod; x*=1ll*x%mod; y>>=1; } return ans; } inline int sum(int x){ return 1ll*(QPow(p[x],b*k[x]+1))*(QPow(p[x]-1,mod-2))%mod; } int main(){ // freopen("sumdiv.in","r",stdin); // freopen("sumdiv.out","w",stdout); T=read(); while(T--){ a=read(),b=read(),cnt=0,ans=1; for(int i=2;i*i<=a;i++) if(!(a%i)){ p[++cnt]=i,k[cnt]=0; while(!(a%i)) a/=i,k[cnt]++; } if(a^1) p[++cnt]=a,k[cnt]=1; for(int i=1;i<=cnt;i++) ans+=sum(i)%mod; write(ans); } return printf("\n"),0; }