#include <bits/stdc++.h> using namespace std; #define ll long long const ll mod=998244353; inline void Read(ll &x) { char ch=getchar();x=0; while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); } bool Check(ll x) { for(int i=2; i*i<=x; i++) if(x%i==0) return 0; return 1; } inline ll qp(ll a,ll b) { int ans=1; while(b) { if(b&1) ans=ans*a%mod; b>>=1,a=a*a%mod; } return ans%mod; } int main() { // freopen("sumdiv.in","r",stdin); // freopen("sumdiv.out","w",stdout); ll a,b,t; bool Sbt5=0,Sbt8=0; Read(t); for(int i=1; i<=t; i++) { Read(a),Read(b); if(i==1) { if(Check(a)) Sbt5=1; if(b==1) Sbt8=1; } if(Sbt5) { printf("%lld\n",qp(a,b+1)*qp(a-1,mod-2)%mod);//? } if(Sbt8) { ll ans=a+1; for(int i=2; i*i<=a; i++) if(a%i==0) ans+=i,ans+=a/i,ans%=mod; printf("%lld\n",ans); //O(t \sqrt a) } } return 0; }