#include<fstream>
#include<iostream>
using namespace std;
int nr_div[1000001],sol[1000009][9];
void ciur()
{
    long long i,j;
    for( i = 2 ;  i <= 1000009 ; i++)
    {
        if(!nr_div[i])
            for(j = i ; j <= 1000009 ; j+=i)
                ++nr_div[j];

        for( j = 1; j <=7 ; j++)
        sol[i][j] = sol[i-1][j];

        if(nr_div[i]<=7 )
            sol[i][nr_div[i]] = i;

    }
}

int main()
{
    ciur();
    ifstream in("divprim.in");
    ofstream out("divprim.out");
    int T,n,k;
    in>>T;
    for( ; T ; --T)
    {
        in>>n>>k;
        out<<sol[n][k]<<"\n";
    }
    in.close();
    out.close();
    return 0;

}