#include <fstream>

using namespace std;

ifstream cin("divprim.in");
ofstream cout("divprim.out");

const int VMAX = 1e6;

int ciur[VMAX+1];



int cb(int v[8][VMAX+2], int ln, int x ){

int st = 1, dr = v[ln][0], rez = st-1;

while(st<=dr){
    int m = (st+dr)/2;
    if(v[ln][m]<=x){
        st=m+1;
        rez=m;
    }
    else{
        dr=m-1;
    }
}
return rez;
}

int m[8][VMAX+2];

int main()
{
    for (int i =2; i<=VMAX;i++){
        if(ciur[i]==0){
            for (int j = i; j<=VMAX;j+=i)
                ciur[j]++;
        }
    }

    for (int i =1; i<=VMAX;i++){
        int x = ciur[i];
        ++m[x][0];

        int nx = m[x][0];
        m[x][nx]=i;

    }
    int t;
    cin>>t;

    for (int i =1; i<=t;i++){
        int n, k;
        cin>>n>>k;
        int cba = cb(m,k,n);
        if(cba == 0)
            cout<<0;
        else
            cout<<m[k][cba];
        cout<<'\n';
    }
    return 0;
}