#include <iostream>
#include <fstream>
#define nmx 1000000
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int t,n,k;
int v[nmx+1],mat[nmx+1][8];
int main()
{
    for(int i=2;i<=nmx;++i)
        if(v[i]==0){
            ++v[i];
            for(int j=2;j*i<=nmx;++j)
                ++v[j*i];
        }
    for(int i=2;i<=nmx;++i)
        for(int j=1;j<=7;++j){
            if(v[i]==j)
                mat[i][j]=i;
            else
                mat[i][j]=mat[i-1][j];
        }
    in>>t;
    for(int i=1;i<=t;++i){
        in>>n>>k;
        out<<mat[n][k]<<"\n";
    }
    return 0;
}