#include <fstream>

using namespace std;

int n[100001], i, j, t, k[100001], p[1000001], maxim, a[1001], d[1001][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]++;      // cati divizori primi are j
                a[divizori[j]]++;   // cate numere au atatia divizori primi cati are j
                d[divizori[j]][a[divizori[j]]] = j;  // j este al a[divizori[j]]-lea numaru care are divizori[j] divizori
            }
    // d[x][y] = al y-lea numar cu x divizori

    for(j=1;j<=t;j++){
        ok=0;
        // in matricea d[k[j]] caut cel mai mare numar mai mic decat n[j]
        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{                   //avem ce afisa
            // CAUTARE BINARA
            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;
}