#include <iostream> #include <cmath> #include <cstdio> using namespace std; bool rec[10000000]={0}; int main() { // freopen("sumdiv.in","r",stdin); // freopen("sumdiv.out","w",stdout); int T, max=0; cin>>T; for (int i=0;i<T;i++) { int m,n; cin>>m>>n; long long res=pow(m,n); long long sum=1+res; for (int j=2;j<=sqrt(res);j++) { if(rec[j]) continue; if (res%j==0) { sum+=j; if(res/j!=j) sum+=res/j; rec[j]=true; } sum%=998244353; } cout<<sum<<endl; } return 0; }