Untitled

#include <iostream>
#include <vector>

using namespace std;

// Hàm kiểm tra số nguyên tố
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    
    return true;
}

// Hàm đếm số cặp số nguyên tố đặc biệt trong khoảng [L, R]
int countSpecialPrimePairs(int L, int R) {
    int count = 0;
    vector<bool> prime(R + 1, true); // Tạo vector prime với kích thước R+1, tất cả giá trị đều là true ban đầu
    
    // Sàng nguyên tố
    for (int p = 2; p * p <= R; p++) {
        if (prime[p]) {
            // Nếu p là số nguyên tố thì đánh dấu các bội của p trong prime là false
            for (int i = p * p; i <= R; i += p) {
                prime[i] = false;
            }
        }
    }
    
    // Đếm số cặp số nguyên tố đặc biệt trong khoảng [L, R]
    for (int i = max(2, L); i <= R - 6; i++) {
        if (prime[i] && prime[i + 6]) {
            count++;
        }
    }
    
    return count;
}

int main() {
    int T;
    cin >> T;
    
    vector<int> results;
    
    // Duyệt qua từng bộ test
    for (int t = 0; t < T; t++) {
        int L, R;
        cin >> L >> R;
        
        // Đếm số cặp số nguyên tố đặc biệt trong bộ test hiện tại
        int count = countSpecialPrimePairs(L, R);
        results.push_back(count);
    }
    
    // In kết quả cho từng bộ test
    for (int t = 0; t < T; t++) {
        cout << results[t] << endl;
    }
    
    return 0;
}