#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
int nrdiv(int x)
{
    int nr=0;
    if(x%2==0)
    {
        while(x%2==0)
            x/=2;
        nr++;
    }
    for(int i=3;i<=x;i++)
    {
        if(x%i==0)
        {
            while(x%i==0)
                x/=i;
            nr++;
        }
    }

    return nr;
}
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int a[100001][2],T,ok,mare;
    f>>T;
    for(int i=0;i<T;i++)
    {
        ok=0;
        f>>a[i][0];
        f>>a[i][1];
        {mare=-1;
            for(int j=2;j<a[i][0];j++)
            {
                if(nrdiv(j)==a[i][1] && j>=mare && j<=a[i][0] )
                {
                    mare=j;
                }

            }
            if(mare==-1)
                g<<0<<"\n";
            else
        g<<mare<<"\n";
        }
    }
    return 0;
}