#include <bits/stdc++.h>
#define XY 1000000
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int a[1000005],d[1000005][8],n,teste,k;
void Ciur()
{
    int i,j;
    for(i=2;i<XY;i=i+2)
        a[i]=1;
    for(i=3;i<XY;i=i+2)
        if(a[i]==0)
        for(j=i;j<XY;j=j+i)
         a[j]++;
}
void Formare()
{
    int i,j;
    for(i=1;i<XY;i++)
        for(j=0;j<8;j++)
        if(a[i]==j)d[i][j]=i;
    else d[i][j]=d[i-1][j];
}
int main()
{
    int i;
    Ciur();
    Formare();
    fin>>teste;
    for(i=1;i<=teste;i++)
    {
        fin>>n>>k;
        fout<<d[n][k]<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}