#include <fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
int divizori_primi(int x) {
    int cnt = 0;
    int d = 2;

    while (d * d <= x) {
        if (x % d == 0) {
            cnt++;
            while (x % d == 0)
                x /= d;
        }
        d++;
    }

    if (x > 1)
        cnt++;

    return cnt;
}

int main() {
    int t;
    cin>>t;

    while (t--) {
        int n, k;
        cin>>n>>k;

        int nr=0;

        for (int i=n; i>=1; i--) {
            if (divizori_primi(i)==k) {
                nr=i;
                break;
            }
        }

        cout<<nr<<"\n";
    }

    return 0;
}