#include <iostream>
#include <fstream>

using namespace std;

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

bool prime(int x){
    if(x < 2 || x > 2 && x % 2 == 0)
        return 0;

    for(int d = 3; d * d <= x; d+= 2)
        if(x % d == 0)
            return 0;

    return 1;
}

int cati_div_primi(int x){
    int counter = 0;

    if(x % 2 == 0)
        counter++;

    if(prime(x) == 1)
        counter++;

    for(int d = 3; d <= x/2; d+=2)
        if(x % d == 0 && prime(d) == 1)
            counter++;

    return counter;
}

int f(int n, int k){
    while(true){

        if(n == 0 || n < 30 && k == 3)
            return 0;
        if(cati_div_primi(n) == k)
            return n;
        n--;

    }
}

int main()
{
    int t, k, n;
    fin >> t;

    for(int i = 0; i < t; i++){

        fin >> n >> k;
        fout << f(n, k) << '\n';

    }

    return 0;
}