#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("divprim.in");
ofstream fout ("divprim.out");

int t,n,k;

bool prim(int x)
{
    if(x==2) return 1;
    if(x%2==0) return 0;
    for(int i=3;i*i<=x;i+=2)
        if(x%i==0)
            return 0;
    return 1;
}

int divpr(int x)
{
    int d=0,i;
    if(x==2) return 1;
    for(i=2;i*i<x;i++)
        if(x%i==0)
            if(prim(i))
            {
                d++;
                if(prim(x/i))
                    d++;
            }

    if(i*i==x) if(prim(i)) d++;
    return d;
}

int main()
{
    fin>>t;
    while(t--)
    {
        int ok=0;
        fin>>n>>k;
        while(n)
        {
            if(divpr(n)==k)
            {
                ok=1;
                fout<<n<<endl;
                break;
            }
            n--;
        }
        if(!ok) fout<<0<<endl;
    }
    return 0;
}