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

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

bitset<1000005> fr;
int n, a[80005], 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++;
        if(nr1 > k) return false;
        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<=maxi; i++)
        if(fr[i] == 0)
            for(j=2; j*i<=maxi; j++)
                fr[j * i] = 1;
    for(i=1; i<=maxi; i++)
        if(fr[i] == 0) a[++m] = i;
    for(i=1; i<=n; i++)
    {
        fin >> x >> k;
        if(fr[x] == 0 && k == 1) fout << x << "\n";
        else
        {
            for(j=x; j>=1 && divi(j) == false; j--)
                ;
            fout << j << "\n";
        }
    }
    fin.close();
    fout.close();
    return 0;
}