#include <iostream>
#include <fstream>

using namespace std;

int div(int a){
    int p=2,f,divprim=0;
    while(a!=1){
        f=0;
        while(a%p==0){
            a/=p;
            f++;
        }
        if (f>0)
            divprim++;
        p++;
    }
    return divprim;
}

int main()
{
    ifstream f ("divprim.in");
    ofstream g ("divprim.out");
    int n;
    f>>n;
    for(int i=0;i<n;i++){
        int a,b,divprim;
        f>>a>>b;
        a--;
        while((div(a)!=b)&&(a>1))
                a--;
        if (a==1)
            g<<0<<endl;
        else
            g<<a<<endl;
    }
}