#include<fstream>
using namespace std;

int div[1000005], sol[1000005][10];

void ciur()
{
    int i, j;
    for(i=2;i<=1000005;i++)
    if(!div[i])
        for(j=i;j<=1000005;j+=i)
        div[j]++;
}
int main()
{
    int n, nr, k, i, j;
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    ciur();
    for(i=2;i<1000001;i++)
    {
        for(j=0;j<=7;j++)
        sol[i][j]=sol[i-1][j];
        sol[i][div[i]]=i;
    }
    f >> nr;
    for(j=1;j<=nr;j++)
    {
        f >> n >> k;
        g << sol[n][k];
    }
    return 0;
}