#include <iostream>
#include <fstream>
using namespace std;
int prim(int x)
{
    int d=2 ,ok=1;
    while(ok==1 && d<=x/2)
    {
        if(x%d==0)ok=0;
        else d++;
    }
    if(ok==1 && x>1)
        return 1;
    else
        return 0;
}
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int T , N , K , ok;
    f>>T;
    for(int i=1 ; i<=T ; i++)
    {
        f>>N>>K;
        int j=N , mx=0;
        while(j>=1)
        {
            int d=2 , s=0 ;
            while(d<=j)
            {
                if(prim(d)==1)
                {
                    if(j%d==0)
                        s++;
                }
                d++;

            }
            if(s==K && j>mx)
            {
                mx=j;
            }
            j--;
        }
        g<<mx<<endl;

    }
    return 0;
}