#include <fstream>
#define IN "divprim.in"
#define OUT "divprim.out"
#define MAX 1000005
 
using namespace std;
 
ifstream in(IN);
ofstream out(OUT);
 
int TEST, N, K;
int ok[MAX], T[MAX][7];
 
void ciur()
{
    int i, j;
    for(i=2; i<=MAX; ++i)
        if(ok[i]==0)
            for(j=i; j<=MAX; j+=i)
                ++ok[j];
    for(i=1; i<=MAX; ++i)
        for(j=1; j<=7; ++j)
            if(ok[i]==j)
                T[i][j]=i;
            else
                T[i][j]=T[i-1][j];
}
 
int main()
{
    in>>TEST;
    ciur();
    while(TEST)
    {
        in>>N>>K;
        if(K>7||K<1)
            out<<"0\n";
        else
            out<<T[N][K]<<'\n';
        --TEST;
    }
    in.close();
    out.close();
    return 0;
}