#include <fstream>

using namespace std;
ifstream cin ("divprim.in");
ofstream cout ("divprim.out");
int a[8][300005],c[1000001],aux[8];
void ciur(){
    c[0]=c[1]=0;
    for(int i=2;i<=1000001;i++)
    if(!c[i])
    for(int j=i;j<=1000001;j+=i)
    c[j]++;
}
void bucket(){
    for(int i=0;i<=1000001;i++)
    a[c[i]][++aux[c[i]]]=i;
}
int cb(int x, int y){
if(x<a[y][1])
return 0;
    int st=1, dr=aux[y],res=0;
    while(st<=dr){
        int mij=(st+dr)/2;
        if(a[y][mij]<=x){
            res=mij;
            st=mij+1;
        }
        else
        dr=mij-1;
    }
    return a[y][res];
}
int main()
{
    int m;
    cin>>m;
    ciur();
    bucket();
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        cout<<cb(x,y)<<'\n';
    }
    return 0;
}