#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iostream>

using namespace std;

const int M = 5000000;
int prime[400000] , mindiv[M];
bool vis[M];

void init() {
    for( int i = 2 ; i < M ; i++ ) {
        if( !vis[i] ) {
            prime[++prime[0]] = i;
            mindiv[i] = prime[0];
        }
        for( int j = 1 ; j <= prime[0] && i*prime[j] < M ; j++ ) {
            vis[i*prime[j]] = 1;
            mindiv[i*prime[j]] = j;
            if( i%prime[j] == 0 )
                break;
        }
    }
}

int main() {
    init();
    long long tot = 0;
    int t , n , d;
    scanf( "%d" , &t );
    while( t-- ) {
        scanf( "%d%d" , &n , &d );
        if( d < M ) {
            printf( "%d\n" , upper_bound( prime+1 , prime+mindiv[d]+1 , (n-1)/d )-prime-1 );
        }
        else {
            int ans = 0;
            for( int j = 1 ; j <= prime[0] && ((long long)prime[j])*d < n ; j++ ) {
                ans++;
                if( d%prime[j] == 0 )
                    break;
            }
            printf( "%d\n" , ans );
        }
    }
    return 0;
}