#include <bits/stdc++.h>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

const int nmax = 1000005;
int n, x, k, V[15];
bool ciur[nmax];

int main()
{
    for(int i = 2; i * i <= nmax - 5; i ++)
        if(ciur[i] == false)
            for(int j = 2 * i; j <= nmax - 5; j += i)
                ciur[j] = true;

    f >> n;
    for(int i = 1; i <= n; i ++)
    {
        f >> x >> k;
        int sol = 1, nr = 0;

        for(int j = sqrt(x); j >= 2 && nr < k; j --)
            if(!ciur[j])
            {
                sol *= j;
                V[++ nr] = j;
            }

        if(nr != k)g << 0 << '\n';
        else
        {
            for(int j = 1; j <= k; j ++)
                if(sol * V[j] <= x)sol *= V[j];

            g << sol << '\n';
        }
    }
    return 0;
}