#include <fstream>

using namespace std;

int n, i, j, t, k, p[1000001];
char ok;
int div[1000002];
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int main(){
    p[0] = p[1] = 1;
    div[1] = div[0] = 0;
    for(i=2;i<=1000000;i++)
        if(p[i] == 0)
            for(j=i+i;j<=1000000;j+=i){
                p[j] = 1;
                div[j]++;
            }
    fin>>t;
    while(t){
        fin>>n>>k;
        ok=0;
        for(i=n;i>=0;i--)
            if(div[i] == k){
                fout<<i<<"\n";
                ok=1;
                break;
            }
        if(ok==0)
            fout<<"0\n";
        t--;
    }
    return 0;
}