#include<fstream>
using namespace std;
int ciur(int x)
{
    int a[1000001],i,j;
    for(i=1;i<=x+1;i++)
    a[i]=0;
    for(i=1;i<=x;i++)
    if(a[i]==0)
    for(j=i+1;j<=x;j+=i)
    a[j]=1;
    return a[x];
}
int divprim(int nr)
{
    int i,s=0;
    for(i=2;i<=nr/2;i++)
    if(nr%i==0&&ciur(i)==1)
    s++;
    return s;
}
int main()
{
    int t,z,k,n,i,ok;
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    f>>t;
    for(z=1;z<=t;z++)
    {
        f>>n>>k;
        ok=1;
        for(i=n;i>=2&&ok==1;i++)
        if(divprim(i)==k)
        {
            g<<i<<"\n";
            ok=0;
        }
        if(ok==1)
        g<<0<<"\n";
    }
    return 0;
}