#include <iostream>
#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
const int maxn=1000005;
int ciur[maxn];
int main()
{
    for(register int i=2;i<maxn;i++)
        ciur[i]=1;
    for(register int i=2;i<=maxn;i++)
        if(ciur[i]==1)
            for(register int j=1;1LL*i*j<=maxn;j++)
                ciur[i*j]++;
    for(register int i=2;i<maxn;i++)
            ciur[i]--;
    int T;
    in>>T;
    for(register int l=1;l<=T;l++)
    {
        int n,k;
        in>>n>>k;
        if(n==0)
            out<<0<<"\n";
        else if(k==0 && n>=1)
            out<<1<<"\n";
        else
        {
            int i=n;
            while(i>=1)
            {
                if(ciur[i]==k)
                {
                    out<<i<<"\n";
                    break;
                }
                i--;
            }
            if(i==0 && ciur[i]!=k)
                out<<0<<"\n";
        }
    }
    return 0;
}