// (⁠◕⁠ᴗ⁠◕⁠✿⁠) // #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #define rep(i, n) for (ll i = 0; i < (n); i++) #define srep(i, s, n) for (ll i = s; i < (n); i++) #define len(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() using namespace std; template using vc = vector; template using vv = vc>; template using vvv = vv>; using vi = vc;using vvi = vv; using vvvi = vv; using ll = long long;using vl = vc;using vvl = vv; using vvvl = vv; using ld = long double; using vld = vc; using vvld = vc; using vvvld = vc; using uint = unsigned int; using ull = unsigned long long; const ld pi = acos(-1.0); const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; // const ll mod = 1000000007; const ll mod = 998244353; inline bool inside(ll y, ll x, ll H, ll W) {return 0 <= (y) and (y) < (H) and 0 <= (x) and (x) < (W); } #define debug(var) do{std::cout << #var << " : \n";view(var);}while(0) template void view(T e){cout << e << endl;} template void view(const vc& v){for(const auto& e : v){ cout << e << " "; } cout << endl;} template void view(const vv& vv){ for(const auto& v : vv){ view(v); } } int op(int a, int b){return a + b;} int e(){return 0;} template struct segtree{ public : segtree(int n) : _n(n){ depth = 0; while ((1 << depth) < _n) depth++; size = 1 << depth; tree = vc(2 * size, e()); } void set(int p, T x){ assert (0 <= p && p < _n); p += size; tree[p] = x; for (int i = 0; i < depth; i++){ p >>= 1; tree[p] = op(tree[2 * p], tree[2 * p + 1]); } return; } T get(int p){ assert(0 <= p && p < _n); return tree[p + size]; } T prod(int l, int r){ assert (0 <= l && l <= r && r <= _n); if (l == r) return e(); T nl = e(), nr = e(); l += size; r += size; while(l < r){ if (l & 1) nl = op(nl, tree[l++]); if (r & 1) nr = op(nr, tree[--r]); l >>= 1; r >>= 1; } return op(nl, nr); } T all_prod(){return tree[1];} private : int _n, depth, size; vc tree; }; vc> querys[1001001]; int main(){ int Q; cin >> Q; rep(i, Q){ int l, r; cin >> l >> r; r++; querys[l].push_back({r, i}); } segtree seg(1001001); rep(i, 1001001) seg.set(i, 1); vi ans(Q, -1); for (int i = 1001000; i >= 1; i--){ for (int j = 2 * i; j < 1001001; j += i) seg.set(j, 0); for (auto [r, id] : querys[i]) ans[id] = seg.prod(i, r); } for (auto x : ans) cout << x << endl; }