#include <cstdio>
using namespace std;

bool fact_primi(int x , int k)
{
    int  cnt=0, lim, d;
    d=2;

    if(x%d==0) cnt++;
    while(x%d==0)
        x=x/d;


    d++;
    while(d*d<=x && x>1)
    {
        if(x%d==0)
        {
            cnt++;
            while(x%d==0)
                x=x/d;

            if(cnt>k) return 0;
        }
        d+=2;
    }
    if(x>1) cnt++;
    if(cnt == k) return 1;
    return 0;
}

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

    int t, i, n,k, max,j;

    scanf("%d", &t);

    for(i=1; i<=t; i++)
    {
        scanf("%d%d", &n, &k);

        max=0;

        for(j=n; j>1; j--)
            if(fact_primi(j,k))
            {
                max=j;
                break;
            }
        printf("%d\n", max);
    }
    return 0;
}