#include<stdio.h>
#include<iostream>
#include<fstream>
using namespace std;
long div[100000],k;
long t,n,i,j,sol[100000][9];

void generare()
{
    for(i=2;i<=100000;i++)
    if(div[i]==0)
    for(j=i;j<=100000;j+=i)
     div[j]++;
    sol[1][0]=1;
 for(i=2;i<=100000;++i)
 {
    for(j=0;j<=7;j++)
    sol[i][j]=sol[i-1][j];
    sol[i][div[i]]=i;
 }
}

int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
 generare();

 f>>t;
 for(i=1;i<=t;i++)
 {
     f>>n>>k;
    g<<sol[n][k]<<endl;
 }
}