#include <fstream>
#include <cmath>
#define nmax 1000005

using namespace std;

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

int c[nmax], v[nmax];

void ciur()
{
    c[0]=c[1]=1;
    for(int i=2; i*i<=nmax; i++)
    {
        if(c[i]==0)
        {
            for(int j=i*i; j<=nmax; j+=i)
            {
                c[j]=1;
            }
        }
    }
}

int rasp(int a)
{
    int nr=0;
    for(int i=1; i<=a; i++)
    {
        if(a%i==0 && c[i]==0)
        {
            nr++;
        }
    }
    return nr;
}

int n, nra, nrb, raspuns;

int main()
{
    in>>n;
    ciur();
    for(int i=1; i<=n; i++)
    {
        in>>nra>>nrb;
        raspuns = 0;
        for(int i=nra; i>=1; i--)
        {
            if(rasp(i)==nrb)
            {
                raspuns = i;
                break;
            }
        }
        out<<raspuns<<"\n";
    }
    return 0;
}