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

int kR = 1;
int n;
ifstream f("divprim.in");
ofstream g("divprim.out");

void rez()
{
    int nr, div;
    f>>nr>>div;
    while(nr>1)
    {
        int aux = nr;
        int nrdiv = 0;
        if(aux%2 == 0)
        {
            nrdiv++;
            while(aux%2 == 0)
            {
                aux/=2;
            }
        }
        for(int i = 3; aux!=1; i+=2)
            if(aux%i == 0)
            {
                nrdiv++;
                while(aux%i == 0)
                {
                    aux/=i;
                }
            }
        if(nrdiv == div)
            break;
        else
            nr--;
    }
    if(nr == 1 || nr == 0)
        g<<0<<"\n";
    else
        g<<nr<<"\n";
}

int main()
{
    f>>n;
    for(int i = 0; i<n; i++)
        rez();
}