#include<bits/stdc++.h> using namespace std; template<typename T>void in(T &a) { T ans=0; char c=getchar(); for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())ans=ans*10+c-'0'; a=ans; } template<typename T,typename... Args>void in(T &a,Args&...args) { in(a),in(args...); } template<typename T>inline T qpow(T a,T b,T n,T ans=1) { for(a%=n;b;b>>=1)(b&1)&&(ans=(ans*a)%n),a=(a*a)%n; return ans%n; } int t; long long a,b; long long solve(long long a,long long b,long long ans=0){ map<long long,long long>v; for(long long i=2;i*i<=a;i++)while(a%i==0)v[i]++,a/=i; if(a!=1)v[a]++; for(map<long long,long long>::iterator it=v.begin();it!=v.end();it++)ans=(ans+((qpow((*it).first,(*it).second*b+1,998244353ll)+998244352)%998244353*qpow((*it).first+998244352,998244351ll,998244353ll)))%998244353; return ans; } int main(){ in(t); while(t--)in(a,b),printf("%lld\n",solve(a,b)); return 0; }