#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

ifstream cinn ("divprim.in");
ofstream coutt ("divprim.out");

int e[100000002],prime[10000002],nmp[100000],k;

void eratostene(){
for(int i=2;i<sqrt(100000000);i++){
    if(e[i] == 0){
        for(int j = 2;j<100000000/i;j++){
            e[i*j] = 1;
        }

    }

}

}

void vectoreratostene(){

for(int i =0;i<100000;i++){
    if(e[i] == 0){
        prime[k] = i;
        k++;
    }
}

}

void NrMultipliiPrimi(){
    for(int i = 0;i<k;i++){
        for(int j = 1;j<k/(i+1);j++){
            nmp[j*prime[i]]+=1;
        }
    }
    for(int i = 0 ;i<k;i++){
       // cout <<nmp[i] << " "<<i<<endl;
    }
}

int main()
{
   int n;
   eratostene();
   vectoreratostene();
   NrMultipliiPrimi();
   cinn >>n;

   for(int i =0;i<n;i++){
        int x,y;
        cinn >> x >>y;

        int j,bec = 1;
        for( j = x ; j>0;j--){
            if(nmp[j] == y+1){
                coutt << j<<endl;
                j = -10;
                bec = 0;
            }

        }
        if(bec == 1){
            coutt << 0 <<endl;
        }

   }

}