#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int N = (int)1e7;
int factor[N + 10], pos[N + 10], cnt_prime[N + 10];
vector <int> prime;
int n, d;

void get_prime() {
    prime.clear();
    cnt_prime[1] = 0;
    for ( int i = 2; i <= N; i ++ ) {
        cnt_prime[i] = cnt_prime[i - 1];
        if ( !factor[i] ) {
            factor[i] = i;
            prime.push_back( i );
            pos[i] = prime.size();
            cnt_prime[i] ++;
        }
        for ( int j = 0; j < (int)prime.size(); j ++ ) {
            if ( prime[j] * i > N ) break;
            factor[prime[j] * i] = i;
            if ( i % prime[j] == 0 ) break;
        }
    }

}
int main() {
    //freopen( "A.in", "r", stdin );

    get_prime();
    int T;
    scanf( "%d", &T );
    while ( T -- ) {
        scanf( "%d%d", &n, &d );
        int tmp = d;
        n --;
        int ret = 0;
        if ( d <= N ) {
            int min_prime = d;
            while ( d != 1 ) {
                min_prime = min( min_prime, factor[d] );
                d /= factor[d];
            }
            ret = pos[min_prime];
            if ( n / tmp <= N ) ret = min( ret, cnt_prime[n / tmp] );
        } else {
            for ( int i = 0; i < (int)prime.size(); i ++ ) {
                if ( prime[i] * d > n ) break;
                ret ++;
                if ( d % prime[i] == 0 ) break;
            }
        }

        cout <<ret<<endl;
    }

    return 0;    
}