#include <bits/stdc++.h>
/// CA SA MA OBISNUIESC CU VECTOR
using namespace std;
#define LMAX 1000000
#define BUF_MAX (1<<18)
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];
bitset <LMAX+5> ciur;
vector<int> List[15];
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]++;
    for(int d=2;d<=LMAX;++d)  List[Div[d]].push_back(d);
    int n;
    scanf("%d ",&n);
    for(int i=1;i<=n;++i){
        int x,k;
        x=GetInt();k=GetInt();
        if(List[k][0]<=x){
            int pos=lower_bound(List[k].begin(),List[k].end(),x+1)-List[k].begin()-1;
            printf("%d\n",List[k][pos]);
        }
        else printf("0\n");
    }
	fclose(stdin);fclose(stdout);
	return 0;
}