#include <iostream>
#include <fstream>
using namespace std;

int NrDiv ( int a ) {
    int d = 2, k = 0;
    while ( a != 1 ) {
    if ( a % d == 0 ) {
        while ( a % d == 0 ) a /= d;
        k++;
    }
    d++;
    }

    return k;
}

int nr ( int n, int k ) {
    for ( int i = n; i >= 2; i--)
        if ( NrDiv(i) == k ) return i;
    return 0;
}

int main()
{
    ifstream fin ( "divprim.in" );
    ofstream fout ( "divprim.out" );
    int n, a, b;
    fin >> n;
    for ( int i = 0; i < n; i++ ) {
        fin >> a >> b;
        fout << nr(a , b) << endl;
    }

    return 0;
}