#include <iostream>
#include<fstream>
#define N 1000000
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int d[N+5];//nr de div a lui i
int sol[N+5][10];//sol[i][j]-cel mai mare<=i nr care are j div

void div()
{
    int i,j;
    for(i=2;i<=N;++i)
        if(!d[i])//daca este prim
        for(j=i;j<=N;j=j+i)
        d[j]++;
}

void solve()
{
    int i,j;
    //completam matricea
    for(i=1;i<=N;++i)
        for(j=1;j<=7;++j)
            if(d[i]==j&&i>sol[i-1][j])
                sol[i][j]=i;
            else sol[i][j]=sol[i-1][j];

}

int main()
{
    int n,x,k,i;
    div();
    solve();
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>x>>k;
        fout<<sol[x][k]<<"\n";
    }

    return 0;
}