#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
using namespace std;
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
const int maxn=100010;
int vis[maxn],d[maxn];
void init(int n) {
    vis[1]=1;
    rep(i,2,n) if(!vis[i]) {
        for(ll j=(ll)i*i;j<=n;j+=i) vis[j]=1;
    }
    rep(i,2,n) d[i]=d[i-1]+(!vis[i]);
}
void solve() {
    int n=read()-1,c=read();
    for(int i=2;i*i<=c&&i*c<=n;i++) if(c%i==0) {
        printf("%d\n",d[i]);
        return;
    }
    printf("%d\n",d[min(c,n/c)]);
}
int main() {
    init(100000);
    dwn(T,read(),1) solve();
    return 0;
}