#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 10000000
using namespace std;
bool check[maxn];
int pr[maxn / 5], mn[maxn];
int tt[maxn];
int tot;
int T;
void euler() {
    memset(check,0,sizeof(check));
    tot=0;
    for(int i=2;i<maxn;i++) {
        if(!check[i]) {
            pr[++tot]=i;
            mn[i] = i;
            tt[i] = 1;
        }
        for(int j=1;j<=tot;j++) {
            if(i*pr[j]>maxn) break;
            check[i*pr[j]]=1;
            
            mn[i*pr[j]] = pr[j];
                
            if(i%pr[j]==0) {
                break;
            } else {
                
            }
        }
    } 
}
int main()
{
    euler();
    tt[0] = 0;
    for (int i = 1; i < maxn; ++ i) tt[i] += tt[i - 1];
    scanf("%d", &T);
    while (T --)
    {
        int n, d, ans;
        scanf("%d%d", &n, &d); n --;
        if (d >= maxn)
        {
            ans = n / d;
            for (int i = 1; pr[i] < ans; ++ i)
                if (d % pr[i] == 0) {ans = pr[i]; break;}
            printf("%d\n", tt[ans]);
        }
        else printf("%d\n", tt[min(n / d, mn[d])]);
    }
}