using namespace std;
#include <fstream>
#include <vector>
#include <set>
FILE *fin=fopen("divprim.in", "r");
ofstream fout("divprim.out");

const int Nmax=1000000;
const int Pmax=79000;
int prim[Nmax];
int p[Pmax], nrp=0;
vector<set<int> > v;
set<int>::iterator it;
set<int> s123;

void eratostene() ;

int main()
{
    int i, n, k, t;
    eratostene();
    for(i=0; i<100; i++) v.push_back(s123);
    for(i=0; i<Nmax; i++)
        v[prim[i]].insert(i);
    fscanf(fin, "%d", &t);
    for(i=0; i<t; i++)
    {
        fscanf(fin, "%d %d", &n, &k);
        it=v[k].lower_bound(n);
        if(it==v[k].begin() && *it!=*(v[k].begin())) fout<<0<<'\n';
        else --it, fout<<*it<<'\n';
    }
    /*for(it=v[3].begin(); it!=v[3].end(); ++it)
        fout<<*it<<' ';*/
    return 0;
}


void eratostene()
{
    int i, j;
    for(i=2; i<Nmax; i++) prim[i]=1;
    for(i=2; i*i<Nmax; )
    {
        while(!prim[i]) i++;
        for(j=i; i*j<Nmax; j++) prim[i*j]=0;
        i++;
    }
    for(i=2; i<Nmax; i++)
        if(prim[i]) p[nrp++]=i;
    for(i=2; i<Nmax; i++) prim[i]=0;
    for(i=0; i<nrp; i++)
        for(j=1; p[i]*j<Nmax; j++)
            prim[p[i]*j]++;
}