#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");

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

int d_pr(int x)
{
    int s=0, i;
    if(x%2==0) s++;
    for(i=3; i<=x; i+=2)
        if(x%i==0 && prim(i)) s++;
    return s;
}

int sol(int x, int k)
{
    int i;
    for(i=x; i>=2; i--)
    {
        if(d_pr(i)==k)
            return i;
    }
    return 0;
}

int main()
{
    int T, N, K;
    f>>T;
    while(T)
    {
        f>>N>>K;
        g<<sol(N, K)<<"\n";
        T--;
    }
    return 0;
}