#include<fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");

#define MAXT 1000000
#define MAXK 7

int nr[MAXK+1][MAXT+1],ciur[MAXT+1];

int main()
{
    int i,j;
    for(i=2; i<=MAXT; i++)
    {
        if(ciur[i]==0)
        {
            for(j=i*2; j<=MAXT; j=j+i)
            {
                ciur[j]++;
            }
            ciur[i]=1;
        }
    }
    for(i=1; i<=7; i++)
    {
        for(j=1; j<=MAXT; j++)
        {
            if(ciur[j]==i)
                nr[i][j]=j;
            else
                nr[i][j]=nr[i][j-1];
        }
    }
    int t;
    cin>>t;
    int n,k;
    for(i=0; i<t; i++)
    {
        cin>>n>>k;
        cout<<nr[k][n]<<'\n';
    }
    return 0;
}