#include <iostream>
#include <stdio.h>

using namespace std;

FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");


int prim[1000005],t,i,n,j,s[1000005][10],k;

void ciur()
{
    int i,j;
    for(i=2;i<=1000000;i++)
    if(!prim[i])
    {
        prim[i]++;
        for(j=i*2;j<=1000000;j+=i)
        prim[j]++;
    }
}

int main()
{
    fscanf(f,"%d",&t);
    ciur();
    for(i=2;i<=1000000;i++)
    {
        for(j=0;j<=7;j++)
        s[i][j]=s[i-1][j];
        s[i][prim[i]]=i;
    }
    for(i=1;i<=t;i++)
    {
        fscanf(f,"%d%d",&n,&k);
        fprintf(g,"%d\n",s[n][k]);
    }
    fclose(g);
    return 0;
}