// TLE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mx = 1001001;

void solve(){
    int q; cin >> q;
    vector<vector<pair<int,int>>> rs(mx);
    for (int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        rs[l].emplace_back(r,i);
    }
    vector<int> ans(q);
    for (auto [r, i] : rs[1]){
        ans[i] = 1;
    }
    vector<bool> ex(mx,true);
    vector<int> buf(mx);
    int bid = 0;
    for (int l = 2; l < mx; l++){
        if (rs[l].empty()) continue;
        ranges::sort(rs[l]);
        int cnt = 0;
        int ir = l;
        for (auto [r, i] : rs[l]){
            while (ir <= r){
                if (ex[ir]){
                    cnt++;
                    buf[bid++] = ir;
                    for (int x = ir*2; x < mx; x += ir){
                        ex[x] = false;
                    }
                }
                ir++;
            }
            ans[i] = cnt;
        }
        while (bid > 0){
            int p = buf[--bid];
            for (int x = p*2; x < mx; x += p){
                ex[x] = true;
            }
        }
    }
    for (int i = 0; i < q; i++){
        cout << ans[i] << '\n';
    }
}

int main(){
    int t = 1;
    // std::cin >> t;
    while (t--){
        solve();
    }
}