#include<algorithm>
#include<iostream>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<bitset>
#include<queue>
#include<cmath>
#include<ctime>
#define inf (1<<30)
#define INF (1ll<<62)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
using namespace std;
typedef long long ll;
template<class T>void sc(T &x){
    int f=1;x=0;char c;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class T>void nt(T x){
    if(!x)return;
    nt(x/10);putchar('0'+x%10);
}
template<class T>void pt(T x){
    if(x<0)putchar('-'),x=-x;
    if(!x)putchar('0');
    else nt(x);
}
int n,m;
const int M=32000;
int prm[M],tot;
bool mark[M+5];
void init(){
    for(int i=2;i<=M;i++){
        if(mark[i])continue;
        prm[++tot]=i;
        for(int j=i*2;j<=M;j+=i)
            mark[j]=true;
    }
}
void solve(){
    sc(n);sc(m);
    int i,ans=0;
    for(i=1;i<=tot&&prm[i]<=m&&1ll*prm[i]*m<n&&1ll*prm[i]*prm[i]<=1ll*m;i++){
        ans++;
        if(m%prm[i]==0)break;
    }
    if(prm[i]*prm[i]>m){
        int l=1,r=tot,res;
        while(l<=r){
            int mid=l+r>>1;
            if(prm[mid]<=m&&1ll*prm[mid]*m<n){
                res=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        ans=res;
    }
    pt(ans);putchar('\n');
}
int main(){
//    freopen("pro.in","r",stdin);
//    freopen("chk.out","w",stdout);
    init();
    int cas;sc(cas);
    while(cas--)solve();
    return 0;
}