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