#include <iostream>
#include <fstream>
/*Miron Ioana Codruta
CN Andrei Saguna
Clasa aXa
[email protected] */

using namespace std;
int maxkdiv(int n,int k)
{
    int m,okg=0;
    for(int i=n;i>=1;i--)
    {

        int p=0,aux=i;
        m=i;
        while(aux%2==0)
            aux/=2,p=1;

        for(int j=3;j<=n;j+=2)
        {
            int ok=0;
            while(aux%j==0)
                aux/=j,ok=1;
                if(ok==1)
                p++;

        }
        if(p==k)
        {
            okg=1;
             break;
        }

    }
    if(okg==1)
    return m;
    else
        return 0;

}
    void citire(int &t,int a[100001],int b[100001])
    {
        ifstream fin("divprim.in");
        fin>>t;
        for(int i=0;i<t;i++)
            fin>>a[i]>>b[i];

    }
    void afis(int t,int a[100001],int b[100001])
    {
         ofstream fout("divprim.out");
        for(int i=0;i<t;i++)
        {
            int c=maxkdiv(a[i],b[i]);
            fout<<c<<"\n";
        }
    }

int main()
{
    int n,k,t,a[100001],b[100001];
    citire(t,a,b);
    afis(t,a,b);

    return 0;
}