/** nume: Sfrijan-Penciu
    prenume: Ilinca
    scoala: Colegiul National "Andrei Saguna"
    clasa: a X-a
    adresa de e-mail: [email protected]
    */
#include <iostream>
#include <fstream>
using namespace std;

int prim (int n)
{
    int i;
    if(n<2||n>2&&n%2==0)
        return 0;
    for(i=3;i*i<=n;i+=2)
        if(n%i==0)
            return 0;
    return 1;
}
int main()
{
    ifstream fin ("divprim.in");
    ofstream fout ("divprim.out");
    int t,n,k,ji,aux,i,j,nr,test;
    fin>>t;
    for(ji=1;ji<=t;ji++)
    {
        fin>>n>>k;
        aux=n;
        for(j=aux;j>=2;j--)
        {
            nr=0;test=0;
            for(i=1;i*i<j;i++)
            {
                if(j%i==0)
                {
                    if(prim(i)==1)
                        nr++;
                    if(prim(j/i)==1)
                        nr++;
                }
            }
            if(i*i==j&&prim(i)==1)
                nr++;
            if(nr==k)
            {
                fout<<j<<"\n";
                test=1;
                break;
            }
        }
        if(test==0)
            fout<<0<<"\n";
        }

    return 0;
}