#include <iostream>
#include <fstream>

using namespace std;

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

void citire(int a[],int b[],int &t)
{
    fin >> t;
    for (int i = 1; i <=t; i++)
    {
        fin >> a[i];
        fin >> b[i];
    }
}

int primalitate(int x)
{
    if (x%2 == 0)
        return 0;
    else for (int d = 3; d*d<=x; d+=2)
        if (x%d == 0)
        return 0;
    return 1;
}

void divizori(int a[], int b[], int t)
{
    for (int i = 1; i <= t; i++)
    {
        int nr;
        int x;
        for (x = a[i]- 1; x >= 2; x--)
        {
        nr = 0;
        if (x%2 == 0)
        nr++;
        for (int d = 3; d*d <= x; d+=2)
            if (primalitate(d) == 1 && x%d == 0)
                nr++;
        }
        if (nr == b[i])
        {
            fout << x << endl;
        }
        else if (nr == 0)
            fout << "0" << endl;
    }
}

int main()
{
    int a[10000], b[10000], t;
    citire(a, b, t);
    divizori(a, b, t);
    return 0;
}