/**
NEAGU Denisa
Colegiul National "Andrei Saguna"
clasa a X-a
[email protected]
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout ("divprim.out");
bool isprime (int n)
{
    if (n<2 || n>2 && n%2==0)
        return false;
    for (int d=3; d*d<=n; d+=2)
    {
        if (n%d==0)
            return false;
    }
    return true;
}
int nrdivp (int x)
{
    if (isprime(x))
        return 1;
    int nr=0, d;
    if (x%2==0)
        nr++;
    if (isprime(x/2)&&x%2==0)
        nr++;
    for (d=3; d*d<x; d+=2)
    {
        if (x%d==0 && isprime(d))
            nr++;
        if (isprime(x/d)&&x%d==0)
            nr++;
    }
    if (d*d==x && isprime(d))
        nr++;
    return nr;

}
int main()
{

    int t, n, k;
    fin>>t;
    while (t)
    {
        fin>>n>>k;
        int nr, ok=0;
        for (nr=n; nr>1; nr--)
        {
            if (nrdivp(nr)==k)
                {fout<<nr<<endl;
                ok=1;
                break;}
        }
        if (ok==0)
            fout<<0<<endl;
        t--;

    }
    return 0;
}