#include <iostream>
#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
const int MAX=1000002;
int ciur[MAX];
int v[8][MAX];
void hatz();
void eratostene()
{
    for(int i=2; i<=MAX; i++)
        if(ciur[i]==0)
            for(int j=i; j<=MAX; j+=i)
                ciur[j]++;
}
void hatz()
{

 for(int i=2; i<=MAX; i++)
        v[ciur[i]][i]=i;
    for(int i=1; i<=7; i++)
        for(int j=2; j<=MAX; j++)
            if(v[i][j]==0) v[i][j]=v[i][j-1];
}
int main()
{
    eratostene();
    hatz();
    int i,t,s,d;
    in>>t;
    for(i=1;i<=t;i++)
    {
        in>>s>>d;
        out<<v[d][s]<<'\n';
    }
    return 0;
}