#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int propr(int x, int y)
{
    int v=0 ,nrdv=0, aux;
    for(v=x; v>0; v--)
    {
        nrdv=0;
        aux=v;
        if(aux%2==0)
        {
            while(aux%2==0)
                aux/=2;
            nrdv++;
        }
        for(int d=3; aux!=1; d+=2)
        {
            if(aux%d==0)
            {
                while(aux%d==0)
                    aux/=d;
                nrdv++;
            }
        }
        if(nrdv==y)
            return v;
    }
    return 0;
}
int main()
{
    int a, b, t, n, k;
    f>>t;
    for(int i=0; i<t; i++)
    {
        f>>a;
        f>>b;
        g<<propr(a,b)<<"\n";
    }
    return 0;
}