#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

const int LIM=700000;
int t, n, k, st[8], dr[8];
struct nr
{
    int val, f;
}v[LIM+1];
void ciur()
{
    v[2].f=1;
    for(int i=4; i<=LIM; i+=2)
        v[i].f++;
    for(int i=3; i<=LIM; i+=2)
        if(!v[i].f)
        {
            v[i].f=1;
            for(int j=i+i; j<=LIM; j+=i)
                v[j].f++;
        }
}
bool cmp(nr a, nr b)
{
    return a.f<b.f or (a.f==b.f and a.val<b.val);
}
int main()
{
    for(int i=1; i<=LIM; ++i)
        v[i].val=i;
    ciur();
    sort(v+1, v+LIM+1, cmp);
    st[0]=1;
    for(int i=2; i<=LIM; ++i)
        if(v[i-1].f!=v[i].f)
        {
            dr[ v[i-1].f ]=i-1;
            st[ v[i].f ]=i;
        }
    dr[7]=n;
    fin>>t;
    while(t--)
    {
        fin>>n>>k;
        int left=st[k], right=dr[k], mj;
        while(left<=right)
        {
            mj=(left+right)/2;
            if(v[mj].val<=n)
                left=mj+1;
            else
                right=mj-1;
        }
        if(v[right].f==k)
            fout<<v[right].val<<'\n';
        else
            fout<<0<<'\n';
    }
    return 0;
}