#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define LL long long
#define INF 0x7FFFFFFF//or 0x3f3f3f3f ?
using namespace std;

template<class T> inline
void read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}

/*============ Header Template ============*/

const int N = 10000000;

bool check[N + 5];
int pr[N / 5], mn[N + 5];
int f[N + 5];
int n, d, ans, tot;

void euler() {
    memset(check, 0, sizeof(check));
    tot = 0;
    for (int i = 2; i < N; i++) {
        if (!check[i]) {
            pr[++tot] = i;
            mn[i] = i;
            f[i] = 1;
        }
        for (int j = 1; j <= tot; j++) {
            if (i * pr[j] > N) break;
            check[i * pr[j]] = 1;
            mn[i * pr[j]] = pr[j];
            if (i % pr[j] == 0) break;
        }
    }
}

int main() {
    euler();
    f[0] = 0; for (int i = 1; i < N; ++ i) f[i] += f[i - 1];
    int T;
    read(T);
    while (T --) {
        read(n), read(d); n --;
        if (d >= N) {
            ans = n / d;
            for (int i = 1; pr[i] < ans; ++ i)
                if (d % pr[i] == 0) {ans = pr[i]; break;}
            printf("%d\n", f[ans]);
        }
        else printf("%d\n", f[min(n / d, mn[d])]);
    }
    return 0;
}