#include <fstream>

using namespace std;

int n[100001], i, j, t, k[100001], p[1000001], maxim, a[10001], d[10001][100], st, dr, mid;
char ok;
int divizori[1000002];
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int main(){

    fin>>t;
    for(i=1;i<=t;i++){
        fin>>n[i]>>k[i];
        if(n[i] > maxim)
            maxim=n[i];
    }

    p[0] = p[1] = 1;
    divizori[1] = 0;
    divizori[0] = 0;
    for(i=2;i<=maxim;i++){

        if(p[i] == 0)
            for(j=i+i;j<=maxim;j+=i){
                p[j] = 1;
                divizori[j]++;
            }
    }

    for(i=0;i<=maxim;i++){
        if(p[i] == 0 || divizori[i] == 1){
            a[1]++;
            d[1][a[1]] = i;
        }
        else{
            a[divizori[i]]++;
            d[divizori[i]][a[divizori[i]]] = i;
        }
    }
    // d[x][y] = al y-lea numar cu x divizori

    for(j=1;j<=t;j++){
        ok=0;

        if(a[k[j]] == 0 || d[k[j]][1] >n[j])    // daca nu exista niciun numar cu k[j] divizori mai mic sau egal cu n[j]
            fout<<"0\n";
        else{

            st=1;
            dr=a[k[j]];
            while(st<=dr){
                mid = (st+dr)/2;
                if(d[k[j]][mid] <= n[j])
                    st=mid+1;
                else
                dr=mid-1;

            }
            fout<<d[k[j]][dr]<<"\n";
        }

    }
    return 0;
}