Untitled

#include <iostream>
#include <vector>

using namespace std;

void sieve_of_eratosthenes(int max_limit, vector<bool> &is_prime, vector<int> &prime_count) {
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= max_limit; i++) {
        is_prime[i] = true;
    }

    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;
            }
        }
    }

    prime_count[0] = 0;
    for (int i = 1; i <= max_limit; i++) {
        prime_count[i] = prime_count[i - 1] + (is_prime[i] ? 1 : 0);
    }
}

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

    const int MAX_LIMIT = 2000000;
    vector<bool> is_prime(MAX_LIMIT + 1);
    vector<int> prime_count(MAX_LIMIT + 1);

    sieve_of_eratosthenes(MAX_LIMIT, is_prime, prime_count);

    while (q--) {
        int l, r;
        cin >> l >> r;

        int count = prime_count[r] - prime_count[l - 1];
        cout << count << endl;
    }

    return 0;
}