#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000000

int ciur[1+MAXN];
int d[1+MAXN][8];

int D(int n, int k){
    if(n==-1)
        return 0;
    if(d[n][k]==0){
        if(ciur[n]==k)
            d[n][k]=n;
        else
            d[n][k]=D(n-1, k);
    }
    return d[n][k];
}

int main(){
    int i, j, n, k;
    FILE*fi,*fo;
    fi=fopen("divprim.in","r");
    fo=fopen("divprim.out","w");
    ciur[0]=ciur[1]=0;
    for(i=2;i*i<=MAXN;i++)
        if(ciur[i]==0){
            for(j=i;j<=MAXN;j+=i)
                ciur[j]++;
        }
    int t;
    fscanf(fi,"%d", &t);
    for(int i=0;i<t;i++){
        fscanf(fi,"%d%d", &n, &k);
        if(k!=0)
            fprintf(fo,"%d\n", D(n, k));
        else if(k==0){
            fprintf(fo,"1\n");
        }
    }
    fclose(fi);
    fclose(fo);
    return 0;
}