/**/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compile and get accepted.
 *      ____________
 *     /            \
 *    /  /\      /\  \
 *   /  /  \    /  \  \
 *   \                /
 *    \     \___/    /
 *     \____________/
 */
const long long mod = 1000000007;
long long mn[1000010];
long long pre[1000010];
void seive(){
    mn[0] = 0;
    mn[1] = 1;
    pre[0] = pre[1] = 0;
    for(long long i = 2ll;i < 1000010;i++){
        pre[i] = pre[i-1];
        if(mn[i])
            continue;
        pre[i]++;
        mn[i] = i;
        for(long long j = i*i;j < 1000010;j+=i){
            if(mn[j])
                continue;
            mn[j] = i;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);

    seive();
    int T;
    cin>>T;
    while(T--){
        long long N,D;
        cin>>N>>D;
        N--;
        if(N <= D){
            cout<<"0\n";
            continue;
        }
        long long res = N/D;
        if(D > 1000010){
            for(int i = 2;i < res;i++){
                if(mn[i] == mn[i] && D%i == 0){
                    res = i;
                    break;
                }
            }
        }else{
            res = min(res,mn[D]);
        }
        cout<<pre[res]<<'\n';
    }
    return 0;
}
/**/