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

const int Nmax=1000000;
const int Pmax=79000;
int n, k;
bool prim[Nmax];
int p[Nmax];
int d[9];
vector<vector<int> > v;
vector<int> v123;

void eratostene() ;
int cauta() ;

int main()
{
    int i, t;
    eratostene();
    fscanf(fin, "%d", &t);
    for(i=0; i<t; i++)
    {
        fscanf(fin, "%d %d", &n, &k);
        fout<<cauta()<<'\n';
        /*it=v[k].lower_ bound(n);
        if(it==v[k].begin() && *it!=*(v[k].begin())) fout<<0<<'\n';
        else --it, fout<<*it<<'\n';*/
    }
    /*for(vector<int>::iterator it=v[1].begin(); it!=v[1].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++;
        p[i]=1;
        for(j=2; i*j<Nmax; j++) prim[i*j]=0, p[i*j]++;
        i++;
    }
    for(i=0; i<9; i++) v.push_back(v123);
    for(i=2; i<Nmax; i++)
        v[p[i]].push_back(i), d[p[i]]++;
    //for(i=0; i<8; i++) sort(v[i].begin(), v[i].end());
}

int cauta()
{
    int st=0, dr=d[k]-1, mijl;
    if(v[k][0]>n) return 0;
    if(v[k][dr]<=n) return v[k][dr];
    while(st<=dr)
    {
        mijl=(st+dr)/2;
        //if(v[k][mijl]==n) return n;
        if(v[k][mijl]<=n && v[k][mijl+1]>n) return v[k][mijl];
        if(v[k][mijl]>n) dr=mijl-1;
        else st=mijl+1;
    }
}//2 3 4 5 7 8 9 11 13