Untitled

#include <iostream>
#include <vector>

using namespace std;

const int MAX_LIMIT = 2000000;
vector<int> prime_count(MAX_LIMIT + 1, 0);

void sieve_of_eratosthenes() {
    vector<bool> is_prime(MAX_LIMIT + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i <= MAX_LIMIT; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAX_LIMIT; j += i) {
                is_prime[j] = false;
            }
        }
    }

    for (int i = 1; i <= MAX_LIMIT; i++) {
        prime_count[i] = prime_count[i - 1] + is_prime[i];
    }
}

int main() {
    int q;
    cin >> q;

    sieve_of_eratosthenes();

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << prime_count[r] - prime_count[l - 1] << endl;
    }

    return 0;
}