#include <iostream>
#include<fstream>
using namespace std;
int nrdivprim(int x,int k)
{
    int p=0,nr=0;
    while(x%2==0)
    {
        x/=2;
        p++;
    }
    if(p>0)
        nr++;
    for(int d=3;d*d<=x;d+=2)
    {
        p=0;
        while(x%d==0)
        {
            x/=d;
            p++;
        }
        if(p>0)
            nr++;
    }
    if(x!=1)
        nr++;
    if(nr==k)
        return 1;
    return 0;
}
int main()
{
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    int t;
    fin>>t;
    for(int i=0;i<t;i++)
    {
        int x,k,rez;
        fin>>x>>k;
        int ok=0;
        int a=x;
        while(ok==0)
        {
            if(a==0)
                break;
            if(nrdivprim(a,k)==1)
            {
                ok=1;
                rez=a;
                break;
            }
            a--;
        }
        if(ok==0)
            rez=0;
        fout<<rez<<endl;
    }
    return 0;
}