#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in"); ofstream g("divprim.out");
int t,n,k,a[9][1000005],b[1000005],lun[9],lt,rt,md;
void ciurmg()
{
    for(int i=2;i<=1000000;++i)
    {
        int x=1000000/i;
        if(b[i]==0)
        for(int j=1;j<=x;++j)
        {
            b[i*j]++;
        }
        if(b[i]<=7)
        {
            lun[b[i]]++;
            a[b[i]][lun[b[i]]]=i;
        }
    }
}
int main()
{
    ciurmg();
    f>>t;
    for(int i=1;i<=t;++i)
    {
        f>>n>>k;
        rt=lun[k];
        lt=0;
        while(rt-lt!=1)
        {
            md=(rt+lt)/2;
            if(a[k][md]>n) rt=md;
            else lt=md;
        }
        g<<a[k][lt]<<"\n";
    }
    return 0;
}