#include <bits/stdc++.h>

using namespace std;

int a[1000005];
int divprim[10][1000005];

void Ciur()
{
    int i,j;
    for(i=2; i <= 1000001; i++)
        if(a[i] == 0)
            for(j=i; j <= 1000001; j+=i) a[j]++;

    for(i=1; i <= 1000001; i++) divprim[a[i]][i] = i;

    for(i=1; i < 8; i++)
        for(j = 1; j <= 1000001; j++) divprim[i][j] = max(divprim[i][j], divprim[i][j - 1]);
}

int main()
{
    int i, t, n, k;
    Ciur();

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

    fin >> t;

    for(i = 1; i <= t; i++)
    {
        fin >> n >> k;
        fout << divprim[k][n] << "\n";
    }
    return 0;
}