#include <bits/stdc++.h>
#define MAXSIZE 1000000
using namespace std;
FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");
int n,k;
char p[MAXSIZE];
int getTheNumber() {
    int i, j, nr = 0;
    for (i = 2; i <= MAXSIZE; ++i) {
      if (p[i] == 0) {
        nr++;
        for (j = i + i; j <= MAXSIZE; j += i) {
          p[j] = 1;
        }
      }
    }
    return nr;
  }
int factori(int a){int p=0,kapa=0;
while(a%2==0){a/=2;p++;}if(p)kapa++;
for(int i=3;i<=sqrt(a);i+=2){p=0;
      while(a%i==0){a/=i;p++;}
      if(p)kapa++;
}
if(a>2)kapa++;
return kapa;
}
int main()
{
    getTheNumber();int T,A,sw;
fscanf(f,"%d",&T);
p[1]=1;
for(int j=1;j<=T;++j){
    fscanf(f,"%d%d",&n,&k);
    sw=0;
    if(k==1){
        for(int i=n;i>=1;--i){
            if(p[i]==0){
             fprintf(g,"%d\n",i);
             sw=1;
             break;
            }
            if(factori(i)==1){
            fprintf(g,"%d\n",i);
            sw=1;
            break;
            }
        }
    }else
    for(int i=n;i>=1;--i){
        if(p[i]==1){
        if(factori(i)==k){
        fprintf(g,"%d\n",i);
        sw=1;
        break;
        }
        }
    }
    if(sw==0)
        fprintf(g,"0\n");
}
}