#include<stdio.h>
using namespace std;
int v[1000001];
int a[8][1000001];
int main(){
    freopen ("divprim.in","r",stdin);
    freopen ("divprim.out","w",stdout);
    int t,n,i,k,x,y;
    a[0][0]=1;
    a[0][1]=1;
    for(i=2;i<=1000000;i++){
        if (v[i]==0)
            for(k=i;k<=1000000;k+=i)
                v[k]++;
        a[v[i]][0]++;
        a[v[i]][a[v[i]][0]]=i;
    }
    scanf ("%d",&t);
    for(i=1;i<=t;i++){
        scanf ("%d%d",&n,&k);
        if (a[k][1]>n) printf ("0\n");
        else {
            x=1;
            y=a[k][0];
            while(x<y-1){
                if (a[k][(x+y)/2]<=n) x=(x+y)/2;
                else y=(x+y)/2;
            }
            printf ("%d\n",a[k][x]);
        }
    }
    return 0;
}