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

int nrdivprimi(int n){
    int d=2,nr=0;

    while (n!=1)
    {
    if(n%d==0){ nr++;
        while(n%d==0) n/=d;
    } else d++;
    }
    return nr;
}

int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int t,n,k;
    f>>t;
    for(int i=0;i<t;i++){
        f>>n>>k;
        while(n!=0){
        if(k==nrdivprimi(n))
            {g<<n<<endl;break;}
        else{
            n--;
        }
        if(n==0) g<<0<<endl;
    }}
    f.close();
    g.close();
    return 0;
}