#include <iostream>
#include <fstream>
#define DMX 1000001
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int t,ciur[DMX],n,k,i,j,mat[8][DMX],l[8];
void mkciur()
{
    for(j=2;j<=(DMX/2);j++)
        if(ciur[j]==0)
        {
            l[1]++;
            mat[1][l[1]]=j;
            for(i=j;i<=DMX-1;i+=j)
                ciur[i]++;
        }
        else
        {
            l[ciur[j]]++;
            mat[ciur[j]][l[ciur[j]]]=j;
        }
}
int caut_bin()
{
    if(n>mat[k][l[k]] && n<mat[k][1]) return 0;
    int lo=1,hi=l[k],mij;
    while(lo<=hi)
    {
        mij=(lo+hi)/2;
        if(mat[k][mij]<=n) lo=mij+1;
        else hi=mij-1;
    }
    return mat[k][hi];
}
int main()
{

    f>>t;
    mkciur();
    for(int m=1;m<=t;m++)
    {
        f>>n>>k;
        g<<caut_bin()<<"\n";
    }
    return 0;
}