#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n, m, ans, T;
int cnt;
LL p[1000005];
bool vis[1000005];
void shai() {
    for (LL i = 2; i <= 1000000; ++i) {
        if (!vis[i]) p[++cnt] = i;
        for (int j = 1; j <= cnt && p[j] * i <= 1000000; ++j) {
            vis[p[j] * i] = true;
            if (i % p[j] == 0)
                break;
        }
    }
}
int main() {
    shai();
    scanf("%I64d", &T);
    while (T--) {
        ans = 0;
        scanf("%I64d%I64d", &n, &m);
        for (int i = 1; i <= cnt; ++i) {
            if (p[i] * m >= n) break;
            if (p[i] > m) break;
            ++ans;
            if (m % p[i] == 0) break;
        }
        printf("%I64d\n", ans);
    }
}