#include <bits/stdc++.h>

using namespace std;
#define LMAX 1000000
int nr_div[LMAX+5];
vector<int> v[105];
void Ciur(){
    int d;
    for(d=2;d<=LMAX;++d)
        if(nr_div[d]==0)
            for(int i=d;i<=LMAX;i+=d)
                ++nr_div[i];
}
int main(){
  //  freopen("divprim.in","r",stdin);
  //  freopen("divprim.out","w",stdout);
    Ciur();
    for(int i=1;i<=LMAX;++i)
        v[nr_div[i]].push_back(i);
    int t;
    scanf("%d",&t);
    while(t--){
        int n,k;
        scanf("%d %d",&n,&k);
        auto p=upper_bound(v[k].begin(),v[k].end(),n);
        if(p==v[k].begin()) printf("0\n");
        else printf("%d\n",*(p-1));
    }
    return 0;
}