#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int ciur[1000001];
int t,n,k;
vector<int> F[20];

int main()
{
    for(int i=2;i<=1000000;i++)
        if(!ciur[i])
            for(int j=1; i*j <=1000000;j++)
                ciur[i*j]++;
    for(int i=1;i<=1000000;i++)
        F[ciur[i]].push_back(i);
    fin>>t;
    for(int q=1;q<=t;q++)
    {
        fin>>n>>k;
        vector<int>::iterator it = upper_bound(F[k].begin(),F[k].end(),n-1);
        if(it == F[k].begin())
            fout<<0<<'\n';
        else
            fout<<*(it-1)<<'\n';
    }
    return 0;
}