#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int n, x, i, j, k, y, m, N, I, c;
bool v[1000000], ciur[40000];
int main()
{
    f>>N;
    v[1]=1;
    for(i=1;i<=1000003;i++)
    {
        j=2;
        if(v[i]=0)
        {
            m++;
            ciur[m]=v[i];
            while(i*j<=1000003)
            {
                v[i*j]=1;
                j++;
            }
        }
    }
    for(I=1;I<=N;I++)
    {
        f>>n;
        f>>k;
        for(j=n-1;j<=1-1;j--)
        {
            y=j;
            c=0;
            x=1;
            while(y>1)
            {
                if(y%ciur[x])
                {
                    c++;
                    while(y%ciur[x]==0)
                    {
                        y=y/ciur[x];
                    }
                }
                x++;
            }
            if(k==c)
            {
                g<<j<<'\n';
                break;
            }
        }
    }
    return 0;
}