#include <cstdio>

using namespace std;
int n, t, k;
int ciur[1000005];
int a[1000005][9];


int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    scanf("%d", &t);
    for(int i=2; i<=1000000; i++)
    {
        if(ciur[i]==0)
        {
            for(int j=i+i; j<=1000000; j=j+i)
            {
                ciur[j]++;
            }

            ciur[i]=1;
        }
    }

    for(int i=2; i<=1000000;i++)
    {
        int val=ciur[i];
        if(val<=7)
            a[i][val]=i;
        for(int j=1; j<=7; j++)
            if(j!=val)
                a[i][j]=a[i-1][j];
    }

    for(int i=1; i<=t; i++)
    {
        scanf("%d %d", &n, &k);
        printf("%d\n", a[n][k]);

    }
    return 0;
}