#include using namespace std; using ll=long long; constexpr int MOD=998244353; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(l);i<(int)(r);i++) #define all(v) v.begin(),v.end() constexpr int MAX_A=100005; namespace Lib{ struct mod_fac{ vector fac,inv,invf; mod_fac (int n): fac(n),inv(n),invf(n){ fac[0]=fac[1]=1; inv[0]=inv[1]=1; invf[0]=invf[1]=1; for(int i=2;ii)primes[j]=i; } } int Q; cin>>Q; Lib::mod_fac F(20*MAX_A); int cntp=0; rep(i,Q){ int A,B; cin>>A>>B; while(A>1){ cntp+=1; A/=primes[A]; } if(cntp>=B){ cout<