#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    int T, N, K;
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    f>>T;


    while (f>>N)
    {
        int nr_div=0, cx, d;
        while (cx!=-1)
        {
            cx=N;
            d=2;
            while (cx>1)
            {
                while (cx%d==0)
                    nr_div++, cx/=d;
            }
            d++;
            f>>K;
            if (nr_div==K)
                g<<N<<endl, cx=-1;
            else
                N--;
        }
        if (cx!=-1)
            g<<'0';
    }


    return 0;
}