#include<stdio.h>
#define N 1000002
int ciur[N+1];
int nr[8][N+1];
int main()
{
    FILE *fin,*fout;
    fin=fopen("divprim.in","r");
    fout=fopen("divprim.out","w");
    int n;
    fscanf(fin,"%d",&n);
    int i;
    for(i=2;i<=1000;i++)
    {
        if(ciur[i]==0)
        {
            int j;
            for(j=i*2;j<=N;j+=i)
                ciur[j]++;
        }
    }
    for(i=1;i<=N;i++)
    {
        int j;
        if(ciur[i]==0&&i!=1)
            ciur[i]=1;
        for(j=0;j<=7;j++)
            nr[j][i]=nr[j][i-1];
        nr[ciur[i]][i]=i;
    }
    for(i=0;i<n;i++)
    {
        int limita,k;
        fscanf(fin,"%d%d",&limita,&k);
        fprintf(fout,"%d\n",nr[k][limita]);
    }
    return 0;
}