stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

vector <bool> prim;

vector <int> vec;

vector <int>::iterator it;

vector <int>::iterator it1;

void prime()

{

    for(int i=0; i<100005; i++)

        prim.push_back(true);

    for(int i=2; i<100005; i++)

    {

        for(int j=2*i; j<100005; j+=i)

            prim[j]=false;

    }

    for(int i=3; i<100005; i+=2)

    {

        int x=(i+1)/2;

        if(prim[i] == true && prim[x] == true)

        {

            vec.push_back(i);

            //cout<<"not"<<endl;

        }



    }

}

int main()

{

    prime();

    //cout<<vec[0]<<endl;

    int q;

    int l,r;

    cin>>q;

    while(q--)

    {

        cin>>l>>r;

        it = lower_bound(vec.begin(),vec.end(),l);

        it1 = upper_bound(vec.begin(),vec.end(),r);

        int pos1=it-vec.begin();

        //cout<<pos1<<endl;

        int pos2 = it1-vec.begin();

        //cout<<pos2<<endl;

        cout<<pos2-pos1<<endl;

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#define df(b, e) ((b) > (e))

#define fore(i, b, e) for(auto i = (b) - df(b, e); i != e - df(b, e); i += 1 - 2 * df(b, e))

#define sz(x) (int) x.size()

#define all(x) x.begin(), x.end()

#define f first

#define s second

#define pb push_back



typedef long long lli;

typedef long double ld;

typedef pair<int, int> ii;



template <class T>

struct rge { T b, e; };



template <class T>

rge<T> range(T i, T j) {

  return rge<T>{i, j};

}



template <class T> auto dud(T *x) -> decltype(cerr << *x, 0);

template <class T> char dud(...);



struct debug {

#ifdef LOCAL

  ~debug() { cout << endl; }



  template <class T>

  typename enable_if<sizeof dud<T>(0) != 1, debug &>::type operator << (T i) {

    cout << boolalpha << i;

    return *this;

  }



  template <class T>

  typename enable_if<sizeof dud<T>(0) == 1, debug &>::type operator << (T i) {

    return *this << range(begin(i), end(i));

  }



  template <class A, class B>

  debug & operator << (pair<A, B> d) {

    return *this << "(" << d.first << ", " << d.second << ")";

  }



  template <class T>

  debug & operator << (rge<T> d) {

    *this << "[";

    for (auto it = d.b; it != d.e; ++it)

      *this << ", " + 2 * (it == d.b) << *it;

    return *this << "]";

  }

#else

  template <class T> 

  debug & operator << (const T&) {

    return *this; 

  }

#endif

};



#define deb(...) " " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " "



const int N = 1e5 + 5;



bitset<N> isp;

int sim[N];

int q, l, r;



int main() {

  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  isp.set();

  isp[0] = isp[1] = 0;

  fore (i, 2, N) {

    if (isp[i]) {

      sim[i] += isp[(i + 1) / 2];

      if (1LL * i * i < N)

        for (int j = i * i; j < N; j += i)

          isp[j] = 0;

    }

    sim[i] += sim[i - 1];

  }

  cin >> q;

  while (cin >> l >> r) 

    cout << sim[r] - sim[l - 1] << '\n';

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std ;



const int MAX = 1e5 + 10 ;



int prime[MAX] , ans[MAX];



int main()

{

	ios_base::sync_with_stdio(0) ;

	cin.tie(0) ;

	for(int i = 0 ; i < MAX ; ++i)

		prime[i] = 1 ; 

	prime[0] = prime[1] = 0 ;

	for(int i = 2 ; i <= MAX ; ++i)

	{

		if(prime[i])

			for(int j = i+i ; j <= MAX ; j += i)

				prime[j] = 0 ;

	}

	for(int i = 3 ; i < MAX ; ++i)

	{

		ans[i] = ans[i-1] + (bool)(prime[i] && prime[(i+1)/2]);

	}

	int q ;

	cin>>q ;

	while(q--)

	{

		int l , r ;

		cin>>l>>r ;

		cout<<ans[r] - ans[l-1]<<"\n";

	}

	return 0 ;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#define df(b, e) ((b) > (e))

#define fore(i, b, e) for(auto i = (b) - df(b, e); i != e - df(b, e); i += 1 - 2 * df(b, e))

#define sz(x) (int) x.size()

#define all(x) x.begin(), x.end()

#define f first

#define s second

#define pb push_back



typedef long long lli;

typedef long double ld;

typedef pair<int, int> ii;



template <class T>

struct rge { T b, e; };



template <class T>

rge<T> range(T i, T j) {

  return rge<T>{i, j};

}



template <class T> auto dud(T *x) -> decltype(cerr << *x, 0);

template <class T> char dud(...);



struct debug {

#ifdef LOCAL

  ~debug() { cout << endl; }



  template <class T>

  typename enable_if<sizeof dud<T>(0) != 1, debug &>::type operator << (T i) {

    cout << boolalpha << i;

    return *this;

  }



  template <class T>

  typename enable_if<sizeof dud<T>(0) == 1, debug &>::type operator << (T i) {

    return *this << range(begin(i), end(i));

  }



  template <class A, class B>

  debug & operator << (pair<A, B> d) {

    return *this << "(" << d.first << ", " << d.second << ")";

  }



  template <class T>

  debug & operator << (rge<T> d) {

    *this << "[";

    for (auto it = d.b; it != d.e; ++it)

      *this << ", " + 2 * (it == d.b) << *it;

    return *this << "]";

  }

#else

  template <class T> 

  debug & operator << (const T&) {

    return *this; 

  }

#endif

};



#define deb(...) " " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " "



const int N = 1e5 + 5;



bitset<N> isp;

int sim[N];

int q, l, r;



int main() {

  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  isp.set();

  isp[0] = isp[1] = 0;

  fore (i, 2, N) {

    if (isp[i]) {

      sim[i] += isp[(i + 1) / 2];

      if (1LL * i * i < N)

        for (int j = i * i; j < N; j += i)

          isp[j] = 0;

    }

    sim[i] += sim[i - 1];

  }

  cin >> q;

  while (cin >> l >> r) 

    cout << sim[r] - sim[l - 1] << '\n';

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

int const N=1e5;

int prime[N];

int ans[N];

int main() {

    //memset(prime,1, sizeof(prime));

    for(int i=2;i<=N;i++)

        prime[i]=1;

    prime[0]=0;prime[1]=0;

for(long long  i=2;i<=N;i++)

{

    if(prime[i]==1)

    {

        //cout<<i;

        for(long long  j=i*i;j<=N;j+=i)

        {



            //cout<<j;

         prime[j]=0;

        }

    }

}



for(int i=3;i<=N;i+=2)

{

   int  x=(i+1)/2;

    if(prime[i]&&prime[x])

    {

       // prime[i]=1;

       ans[i]=1;

   // cout<<"yes";

    }

    else

        ans[i]=0;

   // cout<<i;

}



for(int i=1;i<N;i++)

{

    ans[i]+=ans[i-1];

}



int q;

cin>>q;

while(q--)

{

    int l,r;

    cin>>l>>r;



    cout<<ans[r]-ans[l-1]<<endl;

}

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#define df(b, e) ((b) > (e))

#define fore(i, b, e) for(auto i = (b) - df(b, e); i != e - df(b, e); i += 1 - 2 * df(b, e))

#define sz(x) (int) x.size()

#define all(x) x.begin(), x.end()

#define f first

#define s second

#define pb push_back



typedef long long lli;

typedef long double ld;

typedef pair<int, int> ii;



template <class T>

struct rge { T b, e; };



template <class T>

rge<T> range(T i, T j) {

  return rge<T>{i, j};

}



template <class T> auto dud(T *x) -> decltype(cerr << *x, 0);

template <class T> char dud(...);



struct debug {

#ifdef LOCAL

  ~debug() { cout << endl; }



  template <class T>

  typename enable_if<sizeof dud<T>(0) != 1, debug &>::type operator << (T i) {

    cout << boolalpha << i;

    return *this;

  }



  template <class T>

  typename enable_if<sizeof dud<T>(0) == 1, debug &>::type operator << (T i) {

    return *this << range(begin(i), end(i));

  }



  template <class A, class B>

  debug & operator << (pair<A, B> d) {

    return *this << "(" << d.first << ", " << d.second << ")";

  }



  template <class T>

  debug & operator << (rge<T> d) {

    *this << "[";

    for (auto it = d.b; it != d.e; ++it)

      *this << ", " + 2 * (it == d.b) << *it;

    return *this << "]";

  }

#else

  template <class T> 

  debug & operator << (const T&) {

    return *this; 

  }

#endif

};



#define deb(...) " " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " "



const int N = 1e5 + 5;



bitset<N> isp;

int sim[N];

int q, l, r;



int main() {

  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  isp.set();

  isp[0] = isp[1] = 0;

  fore (i, 2, N) {

    if (isp[i]) {

      sim[i] += isp[(i + 1) / 2];

      if (1LL * i * i < N)

        for (int j = i * i; j < N; j += i)

          isp[j] = 0;

    }

    sim[i] += sim[i - 1];

  }

  cin >> q;

  while (cin >> l >> r) 

    cout << sim[r] - sim[l - 1] << '\n';

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#define MAXNUM 100000

using namespace std;

bool f[MAXNUM + 1];

int c[MAXNUM + 1];

int main(void) {

  for (int i = 2; i <= MAXNUM; i++) {

    if (!f[i]) {

      for (int j = i + i; j <= MAXNUM; j += i) {

        f[j] = 1;

      }

    }

  }

  for (int i = 3; i <= MAXNUM; i++) {

    if (!f[i] && !f[(i + 1) / 2]) c[i] = 1;

  }

  for (int i = 3; i <= MAXNUM; i++) {

    c[i] += c[i - 1];

  }

  int q;

  cin >> q;

  for (int i = 0; i < q; i++) {

    int l, r;

    cin >> l >> r;

    cout << c[r] - c[l - 1] << endl;

  }

  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>





#define dhai_machli ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define endl "\n"

#define ll long long

#define pii pair<int,int>

#define all(x) begin(x), end(x)

#define loop(i,n) for(int i=0; i<n; i++)

#define rep(i,a,b,c) for(int i=a; i<b; i+=c)

#define brep(i,a,b,c) for(int i=a; i>b; i-=c)

#define tc(t) int t; cin>>t; while(t--)

#define sz(v) int((v).size())

#define pb push_back



const int N = 2e5 + 10;





bool f[100001];

int c[100002];



int n, l, r;



using namespace std;



int main()

{







   dhai_machli;







   for ( int i = 2; i * i <= 100000; i ++) if (! f [ i ]) 

      for ( int j = i * i ; j <= 100000; j += i )

            f[ j ] = true ;

   for ( int i = 3; i <= 100000; i += 2) 



      if (! f [ i ] && ! f [( i + 1) / 2]) c [ i ]++;



   for ( int i = 3; i <= 100000; i ++) c [ i ] += c [i - 1];



      

   cin >> n;

   while (n--)

   {

      cin >> l >> r;



      cout << c[r] - c[l - 1] << endl;

   }





   return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#define MAX_R 100000

using namespace std;

int main(void) {

  int q;

  cin >> q;

  vector<int> l(q), r(q);

  for (int i = 0; i < q; i++) {

    cin >> l[i] >> r[i];

  }

  vector<bool> prime(MAX_R + 1, 1);

  vector<int> count(MAX_R + 1, 0);

  prime[0] = prime[1] = 0;

  for (int i = 2; i <= MAX_R; i++) {

    if (prime[i]) {

      for (int j = i * 2; j <= MAX_R; j += i) {

        prime[j] = 0;

      }

    }

  }

  for (int i = 3; i <= MAX_R; i++) {

    if (prime[i] && prime[(i + 1) / 2] && i % 2 == 1) {

      count[i] = count[i - 1] + 1;

    } else {

      count[i] = count[i - 1];

    }

  }

  for (int i = 0; i < q; i++) {

    cout << count[r[i]] - count[l[i] - 1] << endl;

  }

  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>





#define dhai_machli ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define endl "\n"

#define ll long long

#define pii pair<int,int>

#define all(x) begin(x), end(x)

#define loop(i,n) for(int i=0; i<n; i++)

#define rep(i,a,b,c) for(int i=a; i<b; i+=c)

#define brep(i,a,b,c) for(int i=a; i>b; i-=c)

#define tc(t) int t; cin>>t; while(t--)

#define sz(v) int((v).size())

#define pb push_back



const int N = 2e5 + 10;





bool f[100001];

int c[100002];



int n, l, r;



using namespace std;



int main()

{







   dhai_machli;







   for ( int i = 2; i * i <= 100000; i ++) if (! f [ i ]) 

      for ( int j = i * i ; j <= 100000; j += i )

            f[ j ] = true ;

   for ( int i = 3; i <= 100000; i += 2) 



      if (! f [ i ] && ! f [( i + 1) / 2]) c [ i ]++;



   for ( int i = 3; i <= 100000; i ++) c [ i ] += c [i - 1];



      

   cin >> n;

   while (n--)

   {

      cin >> l >> r;



      cout << c[r] - c[l - 1] << endl;

   }





   return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#define MAX_R 100000

using namespace std;

int main(void) {

  int q;

  cin >> q;

  vector<int> l(q), r(q);

  for (int i = 0; i < q; i++) {

    cin >> l[i] >> r[i];

  }

  vector<bool> prime(MAX_R + 1, 1);

  vector<int> count(MAX_R + 1, 0);

  prime[0] = prime[1] = 0;

  for (int i = 2; i <= MAX_R; i++) {

    if (prime[i]) {

      for (int j = i * 2; j <= MAX_R; j += i) {

        prime[j] = 0;

      }

    }

  }

  for (int i = 3; i <= MAX_R; i++) {

    if (prime[i] && prime[(i + 1) / 2]) {

      count[i] = count[i - 1] + 1;

    } else {

      count[i] = count[i - 1];

    }

  }

  for (int i = 0; i < q; i++) {

    cout << count[r[i]] - count[l[i] - 1] << endl;

  }

  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>





#define dhai_machli ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define endl "\n"

#define ll long long

#define pii pair<int,int>

#define all(x) begin(x), end(x)

#define loop(i,n) for(int i=0; i<n; i++)

#define rep(i,a,b,c) for(int i=a; i<b; i+=c)

#define brep(i,a,b,c) for(int i=a; i>b; i-=c)

#define tc(t) int t; cin>>t; while(t--)

#define sz(v) int((v).size())

#define pb push_back



const int N = 2e5 + 10;





bool f[100001];

int c[100002];



int n, l, r;



using namespace std;



int main()

{







   dhai_machli;







   for ( int i = 2; i * i <= 100000; i ++) if (! f [ i ]) 

      for ( int j = i * i ; j <= 100000; j += i )

            f[ j ] = true ;

   for ( int i = 3; i <= 100000; i += 2) 



      if (! f [ i ] && ! f [( i + 1) / 2]) c [ i ]++;



   for ( int i = 3; i <= 100000; i ++) c [ i ] += c [i - 1];



      

   cin >> n;

   while (n--)

   {

      cin >> l >> r;



      cout << c[r] - c[l - 1] << endl;

   }





   return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

using namespace std;



int main() {

    // エラトステネスのふるい

    int MAX = 101010;

    vector<int> is_prime(MAX, 1);

    is_prime[0] = 0, is_prime[1] = 0;

    for (int i = 2; i < MAX; ++i) {

        if (!is_prime[i]) continue;

        for (int j = i*2; j < MAX; j += i) is_prime[j] = 0;

    }



    // 2017-like 数かどうか

    vector<int> a(MAX, 0);

    for (int i = 0; i < MAX; ++i) {

        if (i % 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;

    for (int q = 0; q < Q; ++q) {

        int l, r;

        cin >> l >> r;

        ++r;



        cout << s[r] - s[l] << endl;

    }

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;



typedef long long ll;



int main(void)

{

    int MAX = 101000;

    vector<bool> is_prime(MAX, true);

    is_prime[0] = is_prime[1] = false;

    rep(i, MAX)

    {

        if(!is_prime[i]) continue;

        for(int j = i*2; j < MAX; j += i) is_prime[j] = false;

    }



    vector<bool> a(MAX, false);

    rep(i, MAX)

    {

        if(i%2 == 0) continue;

        if(is_prime[i] && is_prime[(i+1)/2]) a[i] = true;

    }



    vector<int> s(MAX+1, 0);

    rep(i, MAX)

    {

        s[i+1] = s[i];

        if(a[i]) s[i+1]++;

    }



    int q;

    cin >> q;

    rep(i, q)

    {

        int l, r;

        cin >> l >> r;

        cout << s[r+1] - s[l] << endl;

    }



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// AtCoder template

// 見た奴全員saba!

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i,n) for(int i = 0; i < n; ++i)



// 素数判定

// 計算量O(√n)

template<class T>

bool isPrime(T n){

    if(n < 2) return false;

    for(long long i = 2; i*i <= n; ++i) if(n % i == 0) return false;

    return true;

}





// 素数列挙

// nまでの素数をEratosthenesの篩で列挙する

// 計算量O(nloglogn)

template<class T>

vector<T> prime_list(T n){

    vector<T> ret;

    vector<T> isPrime(n+1,1);

    isPrime[0] = isPrime[1] = 0;

    for(long long i = 2; i <= n; ++i){

        if(isPrime[i] == 0) continue;

        ret.push_back(i);

        for(long long j = i*i; j <= n; j += i) isPrime[j] = 0;

    }

    return ret;

    // return isPrime;  // 状況によってはこっちを返す

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    int m = 100001,q; cin >> q;



    vector<int> p = prime_list(m);

    int n = p.size();

    vector<bool> like_list(m+1,false);

    rep(i,n){

        if(isPrime((p[i]+1)/2)) like_list[p[i]] = true;

    }

    like_list[2] = false;

    vector<int> pn_sum(m+1);

    pn_sum[0] = 0;

    rep(i,m){

        if(like_list[i+1]) pn_sum[i+1] = pn_sum[i]+1;

        else pn_sum[i+1] = pn_sum[i];

    }

    

    int l,r;

    rep(i,q){

        cin >> l >> r;

        cout << pn_sum[r] - pn_sum[l-1] << "\n";

    }

}

// Optimized solution to the same problem (faster):
// AtCoder template

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i,n) for(int i = 0; i < n; ++i)



template<class T>

T gcd(T a, T b){

    if(b == 0) return a;

    return gcd(b, a%b);

}



// 素数列挙

// nまでの素数をEratosthenesの篩で列挙する

// 計算量O(nloglogn)

template<class T>

vector<T> prime_list(T n){

    vector<T> ret;

    vector<T> isPrime(n+1,1);

    isPrime[0] = isPrime[1] = 0;

    for(long long i = 2; i <= n; ++i){

        if(isPrime[i] == 0) continue;

        ret.push_back(i);

        for(long long j = i*i; j <= n; j += i) isPrime[j] = 0;

    }

    //return ret;

    return isPrime;  // 状況によってはこっちを返す

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    int q; cin >> q;

    vector<int> isPrime = prime_list(100001);

    vector<int> psum(100002, 0);

    for(int i = 1; i <= 100000; ++i){

        if(isPrime[i] && isPrime[((i+1)/2)]) psum[i+1] = psum[i]+1;

        else psum[i+1] = psum[i];

    }

    int l,r;

    rep(i,q){

        cin >> l >> r;

        cout << psum[r+1]-psum[l-1] << "\n";

    }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int a,b,n;

vector<int> v;

bool prime[501010];

void SieveOfEratosthenes()

{

    int n=401010;



    memset(prime, true, sizeof(prime));



    for (int p=2; p*p<=n; p++)

    {

        if (prime[p] == true)

        {

            for (int i=p*2; i<=n; i += p)

                prime[i] = false;

        }

    }

    for (int p=3; p<=101010; p++)

    {

        if (prime[p] && prime[(p+1)/2])

        {

            v.push_back(p);

        }

    }

}

void init()

{

    SieveOfEratosthenes();

    /*cout<<v.size()<<endl;

    for(int i=0;i<v.size();i++)

    {

        cout<<v[i]<<endl;

    }*/

}

int bcount(int l,int r)

{

    std::vector<int>::iterator low,up;

    low=std::lower_bound (v.begin(), v.end(), l); //          ^

    up= std::upper_bound (v.begin(), v.end(), r); //                   ^

    return (up-v.begin())-(low-v.begin());

}

int main()

{

    init();

    int q,l,r;

    cin>>q;

    for(int i=0;i<q;i++)

    {

        cin>>l>>r;

        cout<<bcount(l,r)<<endl;

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

const int n=1e5+10;

bitset<n> isprime;

vector<int>answer;

void sieve()

{

    isprime[0]=isprime[1]=0;

    for(int p=2; p<=n; ++p)

        if(isprime[p])

            for(int m=2*p; m<n; m+=p)

                isprime[m]=0;



}





int the2017ers[n];

void is2017()

{

    int sum=0;

    for (int p=1; p<=n; p++)

    {

        sum+=(isprime[p]&&isprime[(p+1)/2]);

        the2017ers[p]=sum;



    }



}



int main()

{

     ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    isprime.set();

    sieve();

    is2017();

    int tc,l,r;

    cin>>tc;

    while(tc--)

    {

        cin>>l>>r;

        cout<<the2017ers[r]-the2017ers[l-1]<<endl;

    }





    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

const int mx = 1e5+7;



int ara[mx],prime[mx],cnt[mx];



void sievesolve()

{

    for(int i = 2; i <= mx; i++)

    {

        if(ara[i]== 0)

        {

            prime[i] = 1;

            for(int j = i*2; j < mx; j += i)

                ara[j] = 1;

        }

    }

    for(int i = 1; i < mx; i++)

    {

        if(prime[i] and prime[(i+1)/2]) cnt[i] = 1;

        cnt[i] += cnt[i-1];

    }

}



int main()

{

    sievesolve();

    int t;

    cin >> t;

    while(t--)

    {

        int a , b;

        cin >> a >> b;

        cout << cnt[b] - cnt[a-1] << endl;

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

const int n=1e5+10;

bitset<n> isprime;

vector<int>answer;

void sieve()

{

    isprime[0]=isprime[1]=0;

    for(int p=2; p<=n; ++p)

        if(isprime[p])

            for(int m=2*p; m<n; m+=p)

                isprime[m]=0;



}





int the2017ers[n];

void is2017()

{

    int sum=0;

    for (int p=1; p<=n; p++)

    {

        sum+=(isprime[p]&&isprime[(p+1)/2]);

        the2017ers[p]=sum;



    }



}



int main()

{

     ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    isprime.set();

    sieve();

    is2017();

    int tc,l,r;

    cin>>tc;

    while(tc--)

    {

        cin>>l>>r;

        cout<<the2017ers[r]-the2017ers[l-1]<<endl;

    }





    return 0;

}


// Fastest known solution for this problem: