#include<bits/stdc++.h>
using namespace std;
ifstream F("divprim.in");
ofstream G("divprim.out");
#define D 10000
char b[D];
int p,i,j,t,n,k;
vector<int> c[8];
unsigned char r[1000001];
void C(int &u)
{
    for(u=0;b[p]<'0'||b[p]>'9';)
        if(++p==D)
            F.read(b,D),p=0;
    for(;'0'<=b[p]&&b[p]<='9';) {
        u=u*10+b[p]-'0';
        if(++p==D)
            F.read(b,D),p=0;
    }
}
int main()
{
    for(i=2;i<=1e6;++i)
        if(!r[i])
            for(r[i]=1,j=2;j<=1e6/i;++j)
                ++r[i*j];
    for(i=1;i<=1e6;++i)
        c[r[i]].push_back(i);
    for(C(t);t;--t) {
        C(n),C(k);
        if(c[k][0]<=n)
            G<<c[k][lower_bound(c[k].begin(),c[k].end(),n)-c[k].begin()-1]<<'\n';
        else
            G<<"0\n";
    }
}