#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define DEBUG


const int PRIME_MAX_N = 112345;
class PrimeUtil{
    public:
    // 入力はすべて正とする
    // 素数判定O(√n)
    static bool is_prime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return n != 1; // 1の場合は例外
    }
    // 約数の列挙O(√n)
    static vector<int> divisor(int n) {
        vector<int> res;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                res.push_back(i);
                if (i != n / i) res.push_back(n / i);
            }
        }
        return res;
    }
    // 素因数分解O(√n)
    static map<int, int> prime_factor(int n) {
        map<int, int> res;
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                ++res[i];
                n /= i;
            }
        }
        if (n != 1) res[n] = 1;
        return res;
    }

    static int prime[PRIME_MAX_N]; // i番目の素数
    static bool sieve_is_prime[PRIME_MAX_N + 1]; // is_prime[i]がtrueならiは素数
    // n以下の素数の数を返す
    static int sieve(int n) {
        int p = 0;
        for (int i = 0; i <= n; i++) sieve_is_prime[i] = true;
        sieve_is_prime[0] = sieve_is_prime[1] = false;
        for (int i = 2; i <= n; i++) {
            if (sieve_is_prime[i]) {
                prime[p++] = i;
                for (int j = 2 * i; j <= n; j += i) sieve_is_prime[j] = false;
            }
        }
        return p;
    }
};
int PrimeUtil::prime[PRIME_MAX_N]; // i番目の素数
bool PrimeUtil::sieve_is_prime[PRIME_MAX_N + 1]; // is_prime[i]がtrueならiは素数


void solve(long long Q, std::vector<long long> l, std::vector<long long> r){
    PrimeUtil::sieve(100000);
    // 2017に似た数のリストをつくる
    vector<int> nums;
    for(int i=1; i <= 100000; i++){
        if(i % 2 == 1 && PrimeUtil::sieve_is_prime[i] && PrimeUtil::sieve_is_prime[(i+1)/2]){
            nums.push_back(i);
        }
    }

    // query
    for(int i=0; i < Q; i++){
        int lll;
        // l[i]以上となる一番左のもの
        ll b = -1;
        ll u = nums.size();
        // f(-)は増加。減少なら不等式は>か>=にする。
        while(u - b > 1){
            ll piv = (u + b)/2;
            if(nums[piv] < l[i]){ // 必要なら不等号はとりかえる
                b = piv;
            }else{
                u = piv;
            }
        }
        // bはfがK未満(条件が真)の位置のうち一番右、uはfがK以上(条件が偽)の位置のうち一番左
        lll = u;

        int rrr;
        // r[i]以下となる一番右のもの
        b = -1;
        u = nums.size();
        // f(-)は増加。減少なら不等式は>か>=にする。
        while(u - b > 1){
            ll piv = (u + b)/2;
            if(nums[piv] <= r[i]){ // 必要なら不等号はとりかえる
                b = piv;
            }else{
                u = piv;
            }
        }
        // bはfがK未満(条件が真)の位置のうち一番右、uはfがK以上(条件が偽)の位置のうち一番左
        rrr = b;

        // ans
        int ans = (lll <= rrr ? rrr - lll + 1 : 0);
        cout << ans << endl;
    }

}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long Q;
    scanf("%lld",&Q);
    std::vector<long long> l(Q);
    std::vector<long long> r(Q);
    for(int i = 0 ; i < Q ; i++){
        scanf("%lld",&l[i]);
        scanf("%lld",&r[i]);
    }
    solve(Q, std::move(l), std::move(r));
    return 0;
}


Measured memory_bytes: 2304