#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int T , n , d;
const int N = 1e6 + 10;
int pri[N] , rk[N] , _ , vis[N] , low[N];
void Pre(){
    for(int i=2;i<N;++i){
        if(!vis[i]) rk[i] = _ , pri[_++] = i , low[i] = i;
        for(int j=0,o;j<_&&(o=pri[j]*i)<N;++j){
            vis[o] = true;
            low[o] = pri[j];
            if(i % pri[j] == 0){
                break;
            }
        }
    }
}
void solve1(){
    int t = low[d];
    if(d * 2 > n){
        puts("0");
        return;
    }
    int l = 0 , r = rk[t] + 1;
    while(l + 1 != r){
        int m = (l+r)>>1;
        ll tp = pri[m];
        if(tp * d <= n) l = m;
        else r = m;
    }
    printf("%d\n",l+1);
}

void solve2(){
    int cc = 0;
    for(int i=0;pri[i]*d<=n;++i){
        cc++;
        if(d%pri[i] == 0){
            break;
        }
    }
    printf("%d\n",cc);
}

int main(){
    Pre();
    scanf("%d",&T);
    rep(i,0,T){
        scanf("%d%d",&n,&d);--n;
        if(d <= 1e6) solve1();
        else solve2();
    }
    return 0;
}