#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;


#define N 5000020
#define M 200020
#define mod 1000000007
#define LL long long
#define ls (i << 1)
#define rs (ls | 1)
#define md (ll + rr >> 1)
#define lson ll, md, ls
#define rson md + 1, rr, rs


int readint() {
    char c;
    while((c = getchar()) && !(c >= '0' && c <= '9'));
    int ret = c - 48;
    while((c = getchar()) && (c >= '0' && c <= '9'))
        ret = ret * 10 + c - 48;
    return ret;
}
int p[N], cnt;
bool np[N];
int g[N];

void init() {
    for(int i = 2; i < N; ++i) {
        if(!np[i]) {
            p[cnt++] = i;
            g[i] = i;
        }
        for(int j = 0; j < cnt && i * p[j] < N; ++j) {
            np[i*p[j]] = 1;
            g[i*p[j]] = p[j];
            if(i % p[j] == 0) break;
        }
    }
}
int calc(int x) {
    int v = upper_bound(p, p + cnt, x) - p;
    v--;
    return v + 1;
}

int main() {
    init();
    int cas;
    scanf("%d", &cas);
    while(cas--) {

        int n, d;
        n = readint();
        d = readint();
        n--;
        if(d > n) {
            puts("0");
            continue;
        }
        int ans = 0;
        if(d >= N) {
            int t = n / d;
            int f = -1;
            for(int i = 0; p[i] <= t; ++i) {
                if(d % p[i] == 0) {
                    f = p[i];
                    break;
                }
            }
            if(f == -1) ans = calc(t);
            else ans = calc(f);
        }
        else {
            int t = min(n / d, g[d]);
            ans = calc(t);
        }
        printf("%d\n", ans);
    }
    return 0;
}