#include <stdio.h>
#include <string.h>
#include <iostream>
#define M 40005
using namespace std;
bool mark[M];
int num[M],cnt;
void Init(){
    for(int i=2;i<M;i++){
        if(mark[i])continue;
        num[cnt++]=i;
        for(int j=i;j<M;j+=i)mark[j]=1;
    }
}
int main(){
    int T,i,n,d;
    scanf("%d",&T);
    Init();
    while(T--&&scanf("%d %d",&n,&d)){
        bool flag=0;int x=min(d,(n-1)/d);
        for(i=0;i<cnt&&num[i]<=x;i++){
            if(d%num[i]==0){
                printf("%d\n",i+1);
                flag=1;break;
            }
        }if(!flag)printf("%d\n",i);
    }return 0;
}