#include <fstream>

using namespace std;

int n[100001], i, j, t, k[100001], p[1000001], maxim;
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(j=1;j<=t;j++){
        ok=0;
        for(i=n[j];i>=0;i--)
            if(divizori[i] == k[j]){
                fout<<i<<"\n";
                ok=1;
                break;
            }
        if(ok==0)
            fout<<"0\n";
    }
    return 0;
}