#include<algorithm>
#define DIM 1000001
using namespace std;
int t,c[DIM],sol[11][DIM];
int cbin(int x,int i){
    int m,st,dr,poz;
    for(st=1,dr=sol[i][0],poz=0; st<=dr; ){
        m=(st+dr)/2;
        if(sol[i][m]<=x){
            st=m+1;
            poz=m;}
        else
            dr=m-1;}
    return poz;}
void ciur(){
    int i,j;
    for(i=2; i<=DIM; ++i)
        if(!c[i])
            for(j=i; j<=DIM; j+=i)
                ++c[j];}
void solve(){
    int i,j,n,k,poz;
    for(i=2; i<=DIM; ++i)
        sol[c[i]][++sol[c[i]][0]]=i;
    scanf("%d",&t);
    for(i=0; i<t; ++i){
        scanf("%d%d",&n,&k);
        poz=cbin(n,k);
        if(!poz)
            printf("0\n");
        else
            printf("%d\n",sol[k][poz]);}}
int main(){
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    ciur();
    solve();
    return 0;}