#include<cstdio> 
#include<vector> 
using namespace std; 
int divPrimi[1000001]; 
vector <int> Idiv[8]; 
void NumaraDivPrimi(){   
//calculeaza nr de div primi al tuturor nr pana la 1.000.000         
int i, j;     

for (i = 2; i <= 1000000; i++) 
       if (divPrimi[i] == 0) 
for (j = i; j <= 1000000; j += i) divPrimi[j]++;   
for (i = 2; i <= 1000000; i++)        
if (1 <= divPrimi[i] && divPrimi[i] <= 7)            
Idiv[divPrimi[i]].push_back(i); 
} 
int CautaBinar(int nr, int nrDiv)
{     
int st = 0, dr = Idiv[nrDiv].size() - 1, m;      
    
while (st <= dr){       
m = (st + dr) / 2;         
if (Idiv[nrDiv][m] <= nr && (m + 1 > Idiv[nrDiv].size() - 1 || Idiv[nrDiv][m + 1] > nr)) return Idiv[nrDiv][m];         
else if (Idiv[nrDiv][m] > nr) dr = m - 1;        
else st = m + 1;    
}       
return 0; } 
int main()
{    
freopen("divprim.in", "r", stdin), freopen("divprim.out", "w", stdout);    
int T, x, nrDiv, i;    
scanf ("%d", &T);      
NumaraDivPrimi();  
for (i = 0; i < T; i++){      
scanf ("%d %d", &x, &nrDiv);        
printf("%d\n", CautaBinar(x, nrDiv));  
}  
return 0; }