#include <bits/stdc++.h> using namespace std; const int N=10005,MOD=9901; bool prime[N]; int p[N]; void FindPrime() { for(int i=2,cnt=0; i<N; i++) if(!prime[i]) { p[cnt++]=i; for(int j=i*i; j<N; j+=i) prime[j]=true; } } long long Qpow(long long a,long long b,long long ans=1) { while(b) { if(b&1) ans=(ans*a)%MOD; a=(a*a)%MOD; b>>=1; } return ans; } long long Sum(long long a,long long n) { if(n==0) return 1; long long ans=Sum(a,(n-1)/2); ans=(ans+ans*Qpow(a,(n+1)/2)%MOD)%MOD; return n &1? ans:(ans+Qpow(a,n)%MOD)%MOD; } void Solve(long long A,long long B,long long ans=1) { for(int i=0; p[i]*p[i]<=A; i++) if(A%p[i]==0) { int ai=0; for(; A%p[i]==0; A/=p[i]) ai++; ans=(ans*Sum(p[i],ai*B)%MOD)%MOD; } cout<<(A>1?(ans*Sum(A,B)%MOD)%MOD : ans)<<endl; } int main() { FindPrime(); for(long long A,B,T,cin>>T;T-- ; cin>>A>>B,Solve(A,B)); return 0; }