#include <fstream>
using namespace std;
ifstream f ("divprim.in");
ofstream g ("divprim.out");
int c[1000001],a[10][1000010];
void ciur()
{
    int i,j;
    for(i=2;i<=1000000;i++)
    {
        if(!c[i])
        {
            for(j=2*i;j<=1000000;j+=i)
                c[j]++;
            c[i]=1;
        }
    }
}
int main()
{
    int n,t,k,i,j;
    f>>t;
    ciur();
    for(i=1;i<=7;i++)
    {
        for(j=1;j<=1000000;j++)
        {
            if(c[j]==i)
                a[i][j]=j;
            else a[i][j]=a[i][j-1];
        }
    }
    for(i=1;i<=t;i++)
    {
        f>>n>>k;
        g<<a[k][n]<<"\n";
    }
}