#include <iostream>
#include <fstream>

using namespace std;

bool prim(int x)
{
    int div=3;
    if (x==2)
        return true;
    if(x%2==0)
        return false;
    while (div*div<=x)
    {
        if (x%div==0)
            return false;
        div++;
    }
    return true;
}

int main()
{
    int t, k;
    bool gata=false;
    ofstream g("divprim.out");
    ifstream f("divprim.in");
    f>>t;
    int n;
    for (int i=0; i<t; i++)
    {
        gata=false;
        f>>n>>k;
        for (n; n>0; n--)
        {
            if(gata==false)
            {
                int divizor=2;
                int contor=0;
                while (divizor<n)
                {
                    if (n%divizor==0)
                        if(prim(divizor)==true)
                            contor++;
                    divizor++;
                }
                if (contor==k)
                {
                    g<<n<<endl;
                    gata=true;
                }
                else if (contor != k && n==1)
                {
                    gata=true;
                    g<<0<<endl;
                }
            }
        }
    }
    return 0;
}