#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int prim(int nr)
{
    if(nr<2)
        return 0;
    if(nr%2 && nr!=2)
        return 0;
    for(int i=1;i<=nr/2;i++)
        if(nr%i==0)
            return 0;
    return 1;
}
int abc(int nr,int b)
{
    int n=0,k=nr;
    if(nr==0)
        return 0;

    while(k!=0)
        {
            n=0;
            for(int i=2;i<=k;i++)
                if(k%i==0)
                    if(prim(i)==1)
                        n++;
            if(n==b)
                return k;
            else
                k--;
        }
}
int main()
{
    int n,a,b;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a>>b;
        if(abc(a,b)==b)
            fout<<abc(a,b);
        else
            if(abc(a,b)==0)
                fout<<0<<endl;
    }
    return 0;
}