#include <fstream>

using namespace std;

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

const long long VMAX = 1e3;

long long ciur[VMAX+1];



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

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

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

long long m[8][VMAX+2];

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

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

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

    }
    long long t;
    cin>>t;

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