#include <iostream>
#include <fstream>

using namespace std;
int t,n,k,h,dv1,dv2,dvp,x,y,aux,i;
ifstream fin("");
ofstream fout("");

int main()
{
    cin >> t;
    for (i=1;i<=t;i++)
    {
        cin >> n >> k;
        for (h=n;h>0;h--)
        {
            dvp = 0;
            for (x=2;x<h;x++)
            {
                if (h%x==0)
                {
                    dv2 = 0;
                    for (y=2;y<x;y++) {if(x%y==0){y=x;dv2++;}}
                    if (dv2==0) {dvp = dvp+1;}
                }
            }
            if (dvp==k)
            {
                aux = h;
                h = -1;
            }
        }
        if (h==0) {aux = 0;}
        cout << aux << "\n";
    }
    return 0;
}