#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vec;
typedef priority_queue<int> pq;

#define pb push_back
#define ph push
#define fi first
#define se second

inline void Max(int &a,int b){if(a<b)a=b;}
inline void Min(int &a,int b){if(a>b||a==-1)a=b;}
template<class T>void rd(T &a){
    a=0;char c;
    while(c=getchar(),!isdigit(c));
    do a=a*10+(c^48);
        while(c=getchar(),isdigit(c));
}
template<class T>void nt(T x){
    if(!x)return;
    nt(x/10);
    putchar(48+x%10);
}
template<class T>void pt(T x){
    if(!x)putchar('0');
    else nt(x);
}
inline int Mod_Pow(int x,int a,int mod){
    int res=1;
    for(int i=0;(1ll<<i)<=a;++i){
        if(a&1<<i)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
    }
    return res;
}
const int M=1e6+5;
int prime[M],t;
bool mark[M];
inline void pret(){
    for(int i=2;i<M;++i){
        if(!mark[i])prime[t++]=i;
        for(int j=0;j<t&&1ll*prime[j]*i<M;++j){
            mark[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int n,d,g;
inline bool check(int x){
    return prime[x]<=d&&1ll*prime[x]*d<n;
}
inline void gao(){
    rd(n),rd(d);
    int Mn=0,ans=0;
    for(int i=0;1ll*prime[i]*d<n&&1ll*prime[i]*prime[i]<=d;++i){
        if(d%prime[i]==0){
            Mn=prime[i],ans=i+1;
            break;
        }
    }
    if(!Mn){
        int l=0,r=t-1;
        for(int mid;l<=r;){
            mid=l+r>>1;
            if(check(mid))l=mid+1,ans=mid+1;
            else r=mid-1;
        }
    }
    pt(ans),putchar('\n');
}
int main(){
    int _;
    for(cin>>_,pret();_--;)gao();
}