#include <fstream>

using namespace std;
int ciur[1000005];
int main()
{
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
    for(int i=2; i<=1000000; i++)
    {
        if(ciur[i]==0)
        {
            for(int j=i+i; j<=1000000; j+=i)
            {
                ciur[j]++;
            }
            ciur[i]=1;
        }
    }
    int t, n, k, a, b, m=0;
    cin>>t;
    for(int i=0; i<t; i++)
    {
        cin>>n>>k;
        if(ciur[n]<k && ciur[n+1]<k)
        {
            cout<<0<<endl;

        }
        else
        {
          /*  b=n;
            a=0;
            m=0;
            while(m==0)
            {

                if(ciur[b]==k)
                {
                    cout<<b<<endl;
                    m=1;
                }
                else if(ciur[b/2]<k)
                {
                    b=b/2;
                }

                else
                {
                    a=b/2;
                }
            }*/
            b=n;
            while(ciur[b]!=k)
            {
                b--;
            }
            cout<<b<<endl;
        }
    }

    return 0;
}