#include <iostream>
#include <fstream>

using namespace std;


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


int T, N, K;
int nr_prime[1000000];


void Rezolvare(int N, int K)
{
    int div;

    for (int i = N; i > 0; --i){
        if (i == 1){
            fout << 0 << endl;
            break;
        }
        div = 0;
        for (int j = 0; nr_prime[j] < i; ++j){
            if (i%nr_prime[j] == 0)
                ++div;
        }
        if (div == K){
            fout << i << endl;
            break;
        }
    }
}

void AflareNrPrime()
{
    bool v[1000];
    fill_n(v, 1000, true);

    int contor = 0;

    for (int i = 2; i*i < 1000; ++i){
        for (int j = i*i; j < 1000; j=j+i)
            v[j] = false;
    }

    for (int i = 2; i < 1000; ++i){
        if (v[i] == 1){
            nr_prime[contor] = i;
            ++contor;
        }
    }
}

void Citire()
{
    fin >> T;

    for (int i = 0; i < T; ++i){
        fin >> N >> K;
        Rezolvare(N, K);
    }
}

int main()
{
    AflareNrPrime();
    Citire();
    return 0;
}