#include <stdio.h>
#include <stdlib.h>

int a[8][1000001];
int n,k,p;

void afis()
{
    int i,j;
    for (j=1; j<=20; j++) printf("%3i",j);printf("\n");
    for (i=0; i<=7; i++)
    {
        for (j=1; j<=20; j++) printf("  %i",a[i][j]);
        printf("\n");
    }
}

void solve()
{
    int i,j,x;
    for (i=2; i<=1000000; i++)
    if (a[0][i]==0)
    {
        j=i*2;
        while (j<=1000000)
        {
            a[0][j]++;
            j=j+i;
        }
    }
    for (i=1; i<=7; i++)
    {
        x=0;
        for (j=2; j<=1000000; j++)
        {
           if (a[0][j]==i) x=j;
           a[i][j]=x;
        }
    }

}
int main()
{
    int i;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    solve();
    scanf("%i",&n);
    for (i=1; i<=n; i++)
    {
        scanf("%i%i",&k,&p);
        printf("%i\n",a[p][k]);
    }
    return 0;
}