#include <fstream>

using namespace std;
ifstream f ("divprim.in");
ofstream g ("divprim.out");
int n,i,a[1000005],t,j,k,z;
int main ()
{
    f>>t;
    a[1]=a[0]=0;
    for (i=2;i*i<=1000000;i++)
    {
        if (a[i]==0)
        {
            for (j=i;j<=1000000;j+=i)
                a[j]++;
        }
    }
    for (i=1;i<=t;i++)
    {
         f>>n>>k;
         z=0;
         for (j=n;j>=1 && z==0;j--)
         {
             if (a[j]==k) {
                 g<<j<<'\n';
                 z=1;
             }
         }
         if (z==0) g<<0<<'\n';
    }
    return 0;
}