#include <iostream>
#include <stdio.h>
using namespace std;
char ciur[1000001];
int main(){
    FILE *fin,*fout;
    fin=fopen("divprim.in","r");
    fout=fopen("divprim.out","w");
    int n,i,j,x,k;
    fscanf(fin,"%d\n",&n);
    for(i=2;i<=1000000;i++){
        if(ciur[i]==0){
            for(j=i;j<=1000000;j+=i){
                ciur[j]++;
            }
        }
    }
    for(i=1;i<=n;i++){
        fscanf(fin,"%d%d\n",&x,&k);
        while(ciur[x]!=k &&x>0){
            x--;
        }
        fprintf(fout,"%d\n",x);
    }
    return 0;
}