#include <bits/stdc++.h>

using namespace std;
bool a[1000000002];

int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int n=1000000;
         for (int i=2;i<=n;i++)
    a[i]=1;
for (int i=2;i*i<=n;i++)
 if (a[i])
  for (int j=i;j<=n/i;j++)
     a[i*j]=0;
        int t,k,var=0,rep=0,gasit=0;
        f>>t;
       for(int y=1; y<=t; y++)
        {
            gasit=0;
            f>>n>>k;
                if(n==1)
                    g<<"0"<<'\n';
                    else
                    {

                    int i;
                for( i=n; i>2; --i)
                    {
                        rep=0;
                        for(int j=2; j<=i; j++)
                        {
                            if(a[j]==1 && i%j==0)
                                rep++;
                        }
                                if(rep==k)
                                {
                                    gasit=1;
                                    break;
                                }
                    }
                    if(gasit==1)
                    {
                        g<<i<<'\n';
                    }
                    else
                        g<<"0"<<'\n';
                    }
        }

    return 0;
}