#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
const int vmax=1000001;
int ciur[1000001];
void Ciur()
{
    for(int i=3;i<=vmax;i+=2)
    {
        if(ciur[i]==0)
        for(int j=i*i;j<=vmax;j+=2*i)
            ciur[i]=1;
    }
    ciur[0]=2;
    int j=1;
    for(int i=3;i<=vmax;i++)
    {
        if(ciur[i]==0)
            ciur[j++]=i;
    }
}
int main()
{
    Ciur();
    int n, k, t;
    cin>>t;
    while(t)
    {
        cin>>n>>k;
        while(n)
        {
            int cp=n;
            int l=0;
            int cnt=0;
            while(ciur[l]*ciur[l]<=cp)
            {
                int p=0;
                while(cp%ciur[l]==0)
                {
                    p++;
                    cp=cp/ciur[l];
                }
                if(p!=0)
                {
                    cnt++;
                }
                if(cnt>k)
                    break;
                l++;
            }
            if(cp>1)
                cnt++;
            if(cnt==k || n==1){
                    if(n==1)
                    cout<<0<<endl;
            else
                cout<<n<<endl;
                break;
            }
            n--;
        }
        t--;
    }
    return 0;
}