#include <fstream>
#define NMax 1000000
using namespace std;
ifstream f ("divprim.in");
ofstream g ("divprim.out");

int i, j, t, n, k;
int v[NMax+5], mat[NMax+5][8];

int main ()
{
    v[1]=0;
    for (i=2; i<=NMax; i++){
        if (v[i]==0){
            for (j=1; j*i<=NMax; j++)
                v[i*j]++;
        }
    }

    for (i=1; i<=NMax; i++){
        for (j=0; j<=7; j++){
            if (v[i]==j) mat[i][j]=i;
            else mat[i][j]=mat[i-1][j];
        }
    }

     f >> t;
     for (i=1; i<=t; i++){
        f >> n >> k;
//        g << n << '\n';
        g << mat[n][k] << '\n';
     }
}