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

const int mod = 1000000007;
const int N = 10000010;
int pri[N / 10], num[N], fac[N];
bool a[N];
void init() {
    for (int i = 2, tot = 0; i < N; i++) {
        if (!a[i]) {
            pri[tot++] = i;
            num[i] = 1;
            fac[i] = i;
        }
        for (int j = 0; j < tot && i * pri[j] < N; j++) {
            if (i % pri[j]) {
                a[i * pri[j]] = true;
                fac[i * pri[j]] = pri[j];
            } else {
                a[i * pri[j]] = true;
                fac[i * pri[j]] = pri[j];
                break;
            }
        }
    }
    for (int i = 1; i < N; i++) num[i] += num[i - 1];
}

void read(int &n) {
    char c;
    while (1) {
        c = getchar();
        if (isdigit(c)) break;
    }
    n = c - '0';
    while (1) {
        c = getchar();
        if (isdigit(c)) n = 10 * n + (c - '0');
        else break;
    }
}

int solve(int n, int m) {
    int maxn = n / m;
    if (m < N) return num[min(maxn, fac[m])];
    for (int i = 0; pri[i] <= maxn; i++) {
        if (m % pri[i] == 0) return i + 1;
    }
    return num[maxn];
}

int main()
{
    init();
    int t, n, m;
    scanf("%d", &t);
    while (t--) {
        read(n);
        read(m);
        printf("%d\n", solve(n - 1, m));
    }
    return 0;
}