Crivo

#include <bits/stdc++.h>

using namespace std;
vector <int> primes;
bitset<1000005> bs;
long long tamanho;

void sieve(long long num) {
    tamanho = num + 1;
    bs.set();
    bs[0] = bs[1] = 0;
    for (long long i = 2; i <= tamanho; i++) if (bs[i]) {
        for (long long j = i * i; j <= tamanho; j += i) bs[j] = 0;
        primes.push_back((int)i);
    }
}


int main(){
    sieve(1000010);
    int num;
    cin >> num;
    while(num--){
        int x, y;
        cin >> x >> y;
        int i = 1, cont = 0;
        while (y >= primes[i]){
            if (primes[i] >= x){
                if (primes[i]-primes[i-1] == 2) cont++;
                else if (primes[i+1]-primes[i] == 2)cont++;
            }
            i++;
        }
        cout << cont << endl;
    }
    return 0;
}