#include<iostream>
#include<fstream>
using namespace std;
#define MAX 1000001
ifstream in("divprim.in");
ofstream out("divprim.out");
int d[8][MAX+1],v[MAX+1],n,k,t;
void ciur()
{
    for(int i=2;i<=MAX;i++)
    {
        if(v[i]==0)
        {
            for(int j=i*2;j<=MAX;j=j+i)
                v[j]++;
            v[i]=1;
        }
    }
}
void calc()
{
    for(int i=1;i<=7;i++)
        for(int j=1;j<=MAX;j++)
         if(v[j]==i)
             d[i][j]=j;
        else
            d[i][j]=d[i][j-1];
}
int main()
{
    ciur();
    calc();
    in>>t;
    int a,b;
    for(int i=1;i<=t;i++)
    {
        in>>a>>b;
        out<<d[b][a]<<endl;
    }
}