#include <fstream>
#define N 1000001
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int prime[N],divizori[N];
void ciur()
{
    prime[1]=prime[0]=1;
    for(int i=4;i<=N;i+=2)
        prime[i]=1;
    for(int i=3;i*i<=N;i+=2)
        for(int j=i*i;j<=N;j+=2*i)
            prime[j]=1;
}
void divizor()
{
    for(int i=1;i<=N;i++)
        for(int j=i;j<=N;j+=i)
            if(prime[i]==0)
                divizori[j]++;
}
int main()
{
    ciur();
    divizor();
    int t;
    fin>>t;
    int n,k;
    for(int i=1;i<=t;i++)
    {
        fin>>n>>k;
        int val=0;
        for(int j=n-1;j>=1&&val==0;j--)
            if(divizori[j]==k)
                val=j;
        fout<<val<<"\n";
    }
    return 0;
}