#include <bits/stdc++.h>
using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

bitset<1000005> fr;
int n, a[90005], m, x, k;

bool divi(int b)
{
    int d, nr, p, nr1;
    nr = 1;
    d = a[nr];
    nr1 = 0;
    while(b > 1)
    {
        p = 0;
        while(b % d == 0)
        {
            b /= d;
            p++;
        }
        if(p != 0) nr1++;
        d = a[++nr];
        if(d * d > b && b > 1) d = b;
    }
    return (nr1 == k);
}

int main()
{
    int i, j;
    fin >> n;
    fr[0] = fr[1] = 1;
    for(i=2; i*i<=1000000; i++)
        if(fr[i] == 0)
            for(j=2; j*i<=1000000; j++)
                fr[j * i] = 1;
    for(i=1; i<=1000000; i++)
        if(fr[i] == 0) a[++m] = i;
    for(i=1;i<=n;i++)
    {
        fin >> x >> k;
        for(j=x;j>=1 && divi(j) == false;j--)
            ;
        fout << j << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}