#include <iostream>
#include <stdio.h>
using namespace std;
const int NMAX=1000000;
int ciur[NMAX+5];

int main()
{
    int i,j,n,k,t;
    FILE *fin, *fout;
    fin=fopen("divprim.in", "r");
    fout=fopen("divprim.out", "w");
    ///construirea ciurului:

    for(i=2; i<=NMAX; i=i+2) ciur[i]=1;
    for(i=3; i<=NMAX; i=i+2){
        if(!ciur[i]){
            for(j=i; j<=NMAX; j=j+i)
                ciur[j]++;
        }
    }

    ///determinarea raspunsului
    fscanf(fin, "%d", &t);
    while(t--){
        fscanf(fin, "%d%d", &n, &k);
        i=n;
        while(ciur[i]!=k && i>=2)   i--;
        if(i>=2) fprintf(fout, "%d\n", i);
        else fprintf(fout, "0\n");
    }
    return 0;
}