#include <stdio.h>
#define NMAX 1000005
#define QMAX 100005
 
FILE *f = fopen("divprim.in","rt"), *g = fopen("divprim.out","wt");
 
long int query[QMAX][2],n,i,j,k,pr[NMAX],div[NMAX],T,sol[NMAX][8];
 
 
void citire()
{
fscanf(f,"%ld",&T);
n=0;
for (i=1;i<=T;i++)
    {fscanf(f,"%ld %ld",&query[i][0],&query[i][1]);
    if (query[i][0]>n) n=query[i][0];}
}
 
 
void solve()
{
for (i=1;i<=n;i++)
    {pr[i]=1;div[i]=0;}
for (i=2;i<=n;i++)
    if (pr[i]) {div[i]=1;
            k=2*i;
            while (k<=n)
            {pr[k]=0;
            div[k]++;
            k+=i;
            }
            }
for (i=1;i<=n;i++)
    {
    for (j=1;j<=7;j++)
        sol[i][j]=sol[i-1][j];
    sol[i][div[i]]=i;
    }
 
for (i=1;i<=T;i++)
    fprintf(g,"%ld\n",sol[query[i][0]][query[i][1]]);
}
 
 
 
 
 
int main()
{
citire();
solve();
fclose(f);
fclose(g);
return 0;
}