/*
Popa Alexandru-Ioan
CNI "Grigore Moisil"
[email protected]
Clasa a X-a
*/

#include <iostream>
#include <fstream>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int nrdivprim(int x)
{
    int nr=0, p=0;
    while(x%2==0)
    {
        p++;
        x/=2;
    }
    if(p>0)
        nr++;
    int d=3;
    while(x!=1)
    {
        p=0;
        while(x%d==0)
        {
            p++;
            x/=d;
        }
        if(p>0)
            nr++;
        d+=2;
    }
    return nr;
}

int main()
{
    int T, N, K;
    f>>T;
    for(int i=0; i<T; i++)
    {
        int ok=-1;
        f>>N>>K;
        for(int nr=N; N>0 && ok==-1 && nr>0; nr--)
        {
            if(nrdivprim(nr)==K)
            {
                ok=1;
                g<<nr<<endl;
            }
        }
        if(ok==-1)
            g<<0<<endl;
    }
    return 0;
}