#include <stdio.h>
#define MAX 1000001
#define KMAX 11

//max[i] - cel mai mare numar cu exact i divizori la pasul curent
int t, m[MAX][KMAX], c[MAX], max[KMAX], n, k;

void ciur();

int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);

    ciur();

    scanf("%d", &t);

    while(t--)
    {
        scanf("%d %d", &n, &k);
        printf("%d\n", m[n][k]);
    }
}


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

    max[0] = 1;

    for(i=2;i<MAX;++i)
    {
        max[c[i]] = i;
        for(j=0;j<=KMAX;++j)
        {
            m[i][j] = max[j];
        }
    }
}