#include <bits/stdc++.h>
using namespace std;
#define LMAX 1000000
#define BUF_MAX (1<<14)
char buf[BUF_MAX];
int poz=BUF_MAX;
inline char GetChar(){
    if(poz==BUF_MAX){
        fread(buf,1,BUF_MAX,stdin);
        poz=0;
    }
    return buf[poz++];
}
inline int GetInt(){
    int x=0;char c;
    do{
        c=GetChar();
    }while(!isdigit(c));
    do{
        x=x*10+c-'0';
        c=GetChar();
    }while(isdigit(c));
    return x;
}
char Div[LMAX+5];
int Max[LMAX+5];
bitset <LMAX+5> ciur;
int main(){
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	for(int d=4;d<=LMAX;d+=2) ciur[d]=1;
    for(int d=3;d*d<=LMAX;d+=2)
        if(!ciur[d])
            for(int i=d*d;i<=LMAX;i+=2*d)
                ciur[i]=1;
    for(int d=2;d<=LMAX;++d)
        if(!ciur[d])
            for(int i=d;i<=LMAX;i+=d){
                Div[i]++;
                if(!Max[Div[i]]) Max[Div[i]]=i;
            }
    int n;
    scanf("%d ",&n);
    for(int i=1;i<=n;++i){
        int x,k;
        x=GetInt();k=GetInt();
        if(Max[k]>x||Max[k]==0) printf("0\n");
        else{
            int t=x;
            while(k!=Div[t]) --t;
            printf("%d\n",t);
        }
    }
	fclose(stdin);fclose(stdout);
	return 0;
}