// Nume: Mattia Marziali
// Scoala: Colegiul National Andrei Saguna
// Clasa: 10
// Email: [email protected]

#include <cstdio>
#include <vector>
void fixCiur(std::vector<int>&vec){vec.at(0)=0,vec.at(1)=0;for(unsigned int i=4;i<vec.size();i+=2)vec.at(i)=0;for(unsigned int j=3;j<vec.size();j+=2){if(vec.at(j)==0)continue;for(unsigned int i=j*2;i<vec.size();i+=j)vec.at(i)=0;}}int contDivPrimi(int nr,int req,const std::vector<int> &ciur){int cont=0;for(int i=2;i<=nr;i++){if(ciur.at(i)==1 && nr%i==0){cont++,nr/=i;if(cont>req)return -1;}}return cont;}int solveFor(int value,int req,const std::vector<int> &ciur){for(int i=value-1;i>0;i--)if(contDivPrimi(i,req,ciur)==req)return i;return 0;}int main(){freopen("divprim.in","r",stdin);freopen("divprim.out","w",stdout);std::vector<int> teste;int tnum;scanf("%d",&tnum);int testMax=-1;for(int i=0;i<tnum;i++){int nr,cati;scanf("%d%d",&nr,&cati);teste.push_back(nr);teste.push_back(cati);if(nr>testMax)testMax=nr;}std::vector<int> ciurul;for(int i=0;i<testMax+5;i++)ciurul.push_back(1);fixCiur(ciurul);for(int i=0;i<tnum*2;i+=2)printf("%d\n",solveFor(teste[i],teste[i+1],ciurul));return 0;}