//Navadaru Calin
//CNI GRIGORE MOISIL
// 10
// [email protected]
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int desc_fact(int n , int &nr_div)
{
    int p = 0 , d = 3 , c=0;
    nr_div=1;
    while(n%2==0)
        p++,n/=2;
    if(p!=0)
        c++,nr_div*=(p+1);
    while(n>1)
    {
        p=0;
        while(n%d==0)
            p++,n/=d;
        if(p!=0)
            c++,nr_div*=(p+1);
        d=d+2;
        if(d*d > n && n > 1)
            d=n;
    }
    return c;
}
int main()
{
    int t , n , k;
    f >> t;
    while(t > 0)
    {
        int nr_div=1;
        f >> n >> k;
        if(desc_fact(n,nr_div)==k)
            g << n << "\n";
        else
        {
            bool gasit = false;
            for(int i = n-1 ; i >= 2 && gasit == false ; i--)
            {
                nr_div=1;
                int x;
                x=(desc_fact(i,nr_div));
                if(x==k && nr_div>2)
                {
                    g << i << "\n";
                    gasit = true;
                }
            }
            if(gasit==false)
                g << 0 << "\n";
        }
        t--;
    }
    return 0;
}