#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
#include <cstdio>
#include <tuple>
#include <string>
#include <vector>
#include <set>
#include <string.h>
#include <map>
#include <cmath>
#include <deque>
#include <bitset>
//classのデフォルトアクセス修飾子はprivate
//構造体のデフォルトアクセス修飾子はpublic
//c++では構造体　=　クラス

template<class A,class B> 
struct BB {
    A m_a;
    B m_b;

    void set(A a,B b){
        m_a = a;
        m_b = b;
        return;
    }

    pair<A,B> get(){
        return make_pair(m_a, m_b);
    }

};


template <typename T> // typename は class と書いても良い。
T Add(T a, T b)
{
    return a + b;
}

struct SStudent
{
    char szName[16];
    int nJapanese;
    int nMath;
    int nEnglish;
};

template <class X,class Y> struct AAA {
    X func1(X a){
        return a + a;
    }

    Y func2(Y a)
    {
        return a + a;
    }


};

template <typename T_ret, typename T_p1, typename T_p2> // typename は class と書いても良い。
T_ret Add(T_p1 tp1A, T_p2 tp2B)
{
    return tp1A + tp2B;
}

template <class T>
class Test1
{
public:
    T obj;
};

template <class X, class Y>
class Test2
{
public:
    X obj1;
    Y obj2;
};
//メンバ関数の定義？？？
// X Test2::Add(X t1, X t2) //メンバ関数(setname)の定義
// {
//     return t1 + t2;
// }

//Test2の派生
template <class X, class Y>
class Test3 : public Test2<int, double>
{
};



template <class B, class C>
class Test5 : public Test2<B, C> //テンプレートから派生した新しいテンプレート
{
};

class Pencil
{
private:
    int m_a;
protected:
    int core; // 鉛筆の芯の長さ
public:
    void Write()
    {
        core -= 1; // 書くたびに芯が 1mm ずつ小さくなる
        if (core < 0)
            core = 0;
    }

    void show(){
        cout <<"aaaa" <<endl;
    }
};

class ErasePencil : public Pencil
{
private:
    int rubber; // 消しゴムの大きさ
public:
    ErasePencil()
    {
        core = 10;
        rubber = 20;
    }
    void Erase()
    {
        rubber -= 1; // 消すたびにゴムが 1 立方mm ずつ小さくなる
        if (rubber < 0)
            rubber = 0;
    }

    //オーバーライド
    // void show(){
    //     cout << "残量1：" << core<<" 残量2："<< rubber <<endl;
    // }
};

inline void InitRand()
{
    srand((unsigned int)time(NULL));
}

inline int getRandom()
{
    return rand() % 8 + 1;
}

//i番目の数が素数かどうか判定
 bitset<10000000> is_prime(0);
//ｎ以下の素数を抽出する処理
void primeNumbers(int n ){

    for(int i=2;i <= n;i++) is_prime.set(i);

    for(int i=2;i <= n;i++){
        for(int j = i*2;j < n;j += i){
            is_prime.reset(j);

        }
    }

}

int main(){
    int const MAX = 101010;
    primeNumbers(MAX); //1000以下の素数判定器
    vector<int> a(MAX, 0);
    //2017に似た数の判定
    for (int i = 0; i < MAX; i++)
    {
        if ((i + 1) % 2 != 0)
            continue;
        if (is_prime[i] && is_prime[(i + 1) / 2])
        {
            a[i] = 1;
        }
        
    }

    //累積和
    vector<int> s(MAX + 1, 0);
    for (int i = 0; i < MAX; i++) s[i + 1] = s[i] + a[i];

    //入力出力
    int q;
    cin >> q;
    vector<pair<int,int>> l_r;

    for(int i=0;i < q;i++){
        int r,l;
        cin >> l >> r;
        r++;
        l_r.push_back(make_pair(l,r));
        //cout << s[r] - s[l] << endl;
    }

    for (int i = 0; i < q; i++)
    {
        cout << s[l_r[i].second] - s[l_r[i].first] << endl;
    }

    // //関数
    // int iValue1 = Add<int>(2.6, 1.7);                         // int Add(double, double) が使われます。
    // int iValue2 = Add<double, float, int>(2.6, 1.7);          // double Add(float, int) が使われます。

    // cout << iValue1 <<" " <<iValue2 << endl;

    // cout << "hello kokeshiM0chi" << endl;

    // SStudent students[] = {
    //     {"赤井孝",73,98,86,},
    //     {"笠井大介",64,45,40,},
    //     {"吉田叶",76,78,69,},
    // };

    // //クラス
    // Test1<int> num1;
    // num1.obj = 3.4;

    // Test1<double> num2;
    // num2.obj = 3.4;

    // Test1<string> num3;
    // num3.obj = "aaa";

    // Test2<int,double> num4;//Base
    // num4.obj1 = 3.3;
    // num4.obj2 = 8.8888;

    // Test3<int,double> num5;//派生
    // num5.obj1 = 2.2;
    // num5.obj2 = 9.99999;

    // Pencil a;
    // a.show();

    // ErasePencil er;
    // er.Erase();
    // er.Write();
    // er.show();

    // vector<int> vec_b(10,99);
    // //vec_b.resize(10);
    // int tmp;
    // int num = 119;
    // for (int i = 0; i < 10; i++)
    // {
    //     //vec_b.push_back(i);
    //     vec_b[i] = num--;
    //     if(i == 3){
    //         tmp = vec_b[i];
    //     }
    // }

    // cout <<"書き込み結果" << endl;
    // for (int i = 0; i < vec_b.size(); i++)
    // {
    //     cout << vec_b[i] << endl;
    //     //cout << vec_b.at(i) << endl;
    // }

    // sort(vec_b.begin(), vec_b.end());
    // //int index0 = lower_bound(vec_b.begin(), vec_b.end(), tmp);
    // int index = lower_bound(vec_b.begin(),vec_b.end(),tmp) - vec_b.begin();
    // //cout << "要素番号-0:" << index1 << endl;
    // cout << "要素番号:" << index << endl;

    // cout << "zzzz" << endl;
    // AAA<int, double> tt;
    // cout << tt.func1(3.3) << endl;//6
    // cout << tt.func2(4.4) << endl;//8.8
    // cout << "ggggg" << endl;
    // BB<int,double> b;
    // b.set(3.3,4.44445);
    // pair<int,double> p = b.get();

    // cout << p.first << ":" << p.second;

    //std::vector<int> vec{1, 2, 3};
    // vector<int> vec;
    // vec.push_back(3);
    // vec.push_back(4);
    // vec.push_back(3);
    // for (int i = 0; i < vec.size(); i++){
    //     cout << vec[i] << endl;

    // }

    return 0;
}

Measured memory_bytes: 2292