#include <bits/stdc++.h>

using namespace std;
const int CIFMAX=1e6;
int ciur[CIFMAX+1];
int a[8][CIFMAX];
int main()
{
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    int t,n,k,i,j,nrdiv,nr,mijl,divprim,st,dr,ok;
    fin>>n;
    ciur[0]=ciur[1]=0;
    for(i=2;i<=CIFMAX;i++){
        if(ciur[i]==0){
            for(j=i;j<=CIFMAX;j+=i){
                ciur[j]++;
            }
        }
    }
    for(i=1;i<=7;i++){
        k=1;
        for(j=2;j<=CIFMAX;j++){
            if(ciur[j]==i){
                a[i][k++]=j;
            }
        }
        a[i][0]=k-1;
    }
    for(i=1;i<=n;i++){
        fin>>nr>>divprim;
        if(nr==1){
            fout<<"0"<<"\n";
        }
        else{
            st=1;
            dr=a[divprim][0];
            ok=0;
            while(st<=dr){
                mijl=(st+dr)/2;
                if(a[divprim][mijl]<nr){
                    st=mijl+1;
                    ok=1;
                }
                else{
                    dr=mijl-1;
                }
            }
            if(ok==0){
                fout<<"0"<<"\n";
            }
            else{
                fout<<a[divprim][dr]<<"\n";
            }
        }
    }
    return 0;
}