#include <bits/stdc++.h> using namespace std; const int Mod=998244353; inline int read() { static int 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; } inline int Sum(int n) { long long ans=1; for(int i=2; i*i<=n; i++) if(n%i==0) { int a=1; while(n%i==0) { n/=i; a*=i; } ans=ans*(a*i-1)/(i-1)%Mod; } if(n>1) ans=ans*(1+n)%Mod; return ans%Mod; } inline long long Pow(long long a,long long b) { long long k=1; for(int i=1; i<=b; i++) k=(k*a)%Mod; return k; } int main() { long long T=read(),a,b; while(T--) { a=read(),b=read(); unsigned long long sum=Pow(a,b); sum%=Mod; cout<<Sum(sum)<<endl; } return 0; }