#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int N = 1000005;

int T, n, d;

int pow_mod(int x, int k, int MOD) {
    int ans = 1;
    while (k) {
        if (k&1) ans = 1LL * ans * x % MOD;
        x = 1LL * x * x % MOD;
        k >>= 1;
    }
    return ans;
}

bool mlrb(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 0; i <20; i++) {
        int a = rand() % (n - 1) + 1;
        if (pow_mod(a, n - 1, n) != 1) return false;
    }
    return true;
}

int pri[N], pn, vis[N];

int main() {
    vis[0] = vis[1] = 0;
    for (int i = 2; i < N; i++) {
        if (vis[i]) continue;
        pri[pn++] = i;
        if (1LL * i * i >= 1LL * N) continue;
        for (int j = i * i; j < N; j += i)
            vis[j] = 1;
    }
    scanf("%d", &T);
    while (T--) {
        int ans = 0;
        scanf("%d%d", &n, &d);
        if (d >= 1000000) {
            for (int i = 0; i < pn; i++) {
                if (1LL * pri[i] * d >= 1LL * n) break;
                ans++;
                if (d % pri[i] == 0) break;
            }
        } else if (d >= 0) {
            int Min;
            if (vis[d] == 0) Min = d;
            else {
                for (int i = 0; i < pn; i++) if (d % pri[i] == 0) {
                    Min = pri[i];
                    break;
                }
            }
            Min = min(Min, (n - 1) / d);
           // printf("%d\n", Min);
            int cnt = upper_bound(pri, pri + pn, Min) - pri;
            ans = max(0, cnt);
        } else {
            for (int i = 0; i < pn; i++) {
                if (1LL * pri[i] * d >= 1LL * n) break;
                ans++;
                if (d % pri[i] == 0) break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}