/*Chitea Razvan
Colegiul National "Andrei Saguna"
a X-a
[email protected]*/

#include <fstream>

using namespace std;

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

long long diprim (long long  n, long long  k)
{
    long long  a, c, ok;
    while(n-1)
    {
        a=n-1, ok=0, c=0;
        long long  d=3;
        while(a%2==0)
        {
            ok=1;
            a/=2;
        }
        if(ok)
            c++;
        while(a>1)
        {
            ok=0;
            while(a%d==0)
            {
                ok=1;
                a/=d;
            }
            if(ok)
                c++;
            d+=2;
        }
        if(c==k)
            return n-1;
        n--;
    }
    return 0;
}

int main()
{
    long long  t, n, k;
    fin >> t;
    for(long long  i=1; i<=t; i++)
    {
        fin >> n >> k;
        fout << diprim(n+1, k) << "\n";
    }
    return 0;
}