#include <iostream>
#include<fstream>
using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");
int nr_divprim(int x)
{
    int nr=0,d=2,e=0,aux=x;
    if(x==1)
        return 0;
    while(x%d==0)
    {
        e++;
        x/=d;
    }
    if(e>=1)
        nr++;
    for(d=3;d*d<=x;d+=2)
    {
        e=0;
        while(x%d==0)
    {
        e++;
        x/=d;
    }
    if(e>=1)
        nr++;
    }
   if(x!=aux && x!=1)
      nr++;
    return nr;
}

int main()
{
    int N,K,T;
    f>>T;
    for(int i=0;i<T;i++)
    {
        f>>N>>K;
        int X=N,ok=0;
        while(X>1 && ok!=1)
            if(nr_divprim(X)==K)
               {g<<X<<"\n";ok=1;}
             else X--;
        if(ok==0)
            g<<0<<"\n";
    }


    return 0;
}