#include <bits/stdc++.h>

#define REP(i, n) for(decltype(n) i = 0; i < n; i++)

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

const int MOD  = (int)1e9 + 7;
const int INF  = (int)1e9 + 1;
const ll  LINF = (ll)1e18 + 1;

class PrimeNumberCalculator {
    using ull = unsigned long long;
public:
    PrimeNumberCalculator() = default;
    explicit PrimeNumberCalculator(const ull& n_max) :
        list_(generate(std::sqrt(n_max))),
        n_max_(n_max) { }

    /**
     *  素数を生成する
     *  @n_max:  値の最大値
     *  @Return: n_max以下の素数
     */
    std::vector<ull> generate(const ull& n_max) const {
        std::vector<uint> table(n_max + 1, 0);
        std::vector<ull> list;
        for(ull i = 2; i <= n_max; i++) {
            if(table[i] == 0) {
                list.push_back(i);
                for(uint j = i; j <= n_max; j+=i) {
                    table[j] = 1;
                }
            }
        }
        return list;
    }

    /**
     *  素数であるかどうかを判定する
     *  @n:      入力
     *  @Return: 素数であればtrueを返す
     */
    bool check(const ull& n) {
        validate(n);
        ull n_max = std::sqrt(n);
        for(const auto& v : list_) {
            if(n_max < v) {
                break;
            }
            else if(n % v == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     *  素因数分解を行い、底とその冪指数を返す
     *  @n:      入力
     *  @Return: key :: 底(素数), value :: 冪指数
     */
    std::map<ull, ull> generatePrimeFactorizationMap(ull n) {
        validate(n);
        std::map<ull, ull> prime_cnt_map;
        ull n_max = std::sqrt(n);
        for(const auto& v : list_) {
            if(n_max < v) {
                break;
            }
            while(n % v == 0) {
                n /= v;
                auto itr = prime_cnt_map.find(v);
                if(itr != prime_cnt_map.end()) {
                    itr->second++;
                }
                else {
                    prime_cnt_map.emplace(v, 1);
                }
            }
        }
        if(1 < n) {
            prime_cnt_map.emplace(n, 1);
        }
        return prime_cnt_map;
    }

    /**
     *  約数の個数を返す
     *  @n:      入力
     *  @Return: 約数の個数
     */
    ull calcNumOfDivisor(ull n) {
        ull  num = 1;
        auto map = generatePrimeFactorizationMap(n);
        for(const auto& v : map) {
            num *= (v.second + 1);
        }
        return num;
    }

    /**
     *  約数の総和を返す
     *  @n:      入力
     *  @Return: 約数の総和
     */
    ull calcSumOfDivisor(ull n) {
        ull sum   = 1;
        auto map = generatePrimeFactorizationMap(n);
        for(const auto& v : map) {
            ull t     = 1;
            ull t_sum = 1;
            for(ull i = 0; i < v.second; i++) {
                t     *= v.first;
                t_sum += t;
            }
            sum *= t_sum;
        }
        return sum;
    }

private:
    std::vector<ull> list_;
    ull              n_max_;

    /**
     *  前計算で導出しているテーブルのvalidateを行う
     *  @n:      対象の入力
     *  @Return: void
     */
    void validate(const ull& n) {
        if(n_max_ < n) {
            list_  = generate(std::sqrt(n));
            n_max_ = n;
        }
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    const int MAX = 100000;

    PrimeNumberCalculator p;
    auto pn = p.generate(MAX);

    vector<int> table(MAX + 1, 0);
    for(const auto& v : pn) {
        if(v % 2 == 1 &&
           binary_search(ALL(pn), (v + 1) / 2)) {
            table[v]++;
        }
    }

    for(int i = 1; i <= MAX; i++) {
        table[i] += table[i - 1];
    }

    int Q;
    std::cin >> Q;
    REP(i, Q) {
        int l, r;
        std::cin >> l >> r;
        std::cout << table[r] - table[l - 1] << "\n";
    }

    return 0;
}


Measured memory_bytes: 1144