#include <iostream>
#include<fstream>
using namespace std;

int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int T,N,K,ok,d1,d,nr,j;
    f>>T;
    for(int i=1; i<=T; i++)
    {
        f>>N>>K;
        for(int j=N; j>=1; j--)
        {
            d1=2;
            nr=0;
            while(j)
            {
                if(j%d1==0)
                {
                    ok=1,d=2;
                    while(ok==1 && d<=d1/2)
                        if(d1%d==0)
                            ok=0;
                        else
                            d++;
                    if(ok==1 && d1>1)
                        nr++;
                }
                d1++;
                if(d1>j)
                    break;
            }

            if(nr==K)
            {
                g<<j<<" ";
                break;
            }

        }
        if(nr==0)
            g<<0<<" ";
    }

    return 0;
}