stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

using P = pair<ll,ll>;

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

const ll INF = 999999999999999;



vector<bool> isPr;



//0からnまでの数字が素数かどうかを表す配列isPr

void isPrime( ll n ){

  isPr.assign(n+1,true);

  isPr.at(0) = false;

  isPr.at(1) = false;

  isPr.at(2) = true;

  for(ll now=2;now<=n;++now){

    if( isPr.at(now) ){

      ll cnt = 2;

      while( now*cnt <= n ){

        isPr.at(now*cnt) = false;

        cnt++;

      }

    }

  }

}



int main(){

  ll q;

  cin >> q;

  isPrime(100000);

  vector<ll> sum(100001);

  ll now = 0;

  for(ll i=1;i<=100000;i+=2){

    if( isPr.at(i) && isPr.at((i+1)/2) ){

      ++now;

      sum.at(i) = now;

      sum.at(i+1) = now;

    }else{

      sum.at(i) = now;

      sum.at(i+1) = now;

    }

  }

  rep(i,q){

    ll l,r;

    cin >> l >> r;

    ll ans;

    if( isPr.at(l) && isPr.at((l+1)/2) ){

      ans = sum.at(r)-sum.at(l)+1;

    }else{

      ans = sum.at(r)-sum.at(l);

    }

    printf("%lld\n",ans);

  }

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.134848061626015x):
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

using P = pair<ll,ll>;

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

const ll INF = 999999999999999;



vector<bool>  b(100001,true);

vector<ll> sum(100001);



void func(){

  b.at(0) = false;

  b.at(1) = false;

  

  for(ll i=2;i<=(ll)sqrt(100000)+1;++i){

    if( b.at(i) ){

      ll cnt = 2;

      while( i*cnt <= 100000 ){

        b.at(i*cnt) = false;

        ++cnt;

      }

    }

  }

  ll num=0;

  for(ll i=1;i<=100000;i+=2){

    if( b.at(i) && b.at((i+1)/2) ){

      sum.at(i-1) = num;

      ++num;

      sum.at(i) = num;

    }else{

      sum.at(i-1) = num;

      sum.at(i) = num;

    }

  }

}

int main(){

  ll q;

  cin >> q;

  func();

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

    ll l,r;

    cin >> l >> r; 

    cout << sum.at(r) - sum.at(l-1) << "\n";

  }

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

int main() {

    vector<int> prime(100010, true);

    prime.at(1) = false;

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

        if(prime.at(i)) {

            for(int j = i*2; j <= 100000; j += i) prime.at(j) = false;

        }

    }

    

    vector<int> like2017(100010);

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

        if(i%2==1&&prime.at(i)&&prime.at((i+1)/2)) like2017.at(i) = like2017.at(i-1) + 1;

        else like2017.at(i) = like2017.at(i-1);

    }

    

    int Q; cin >> Q;

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

        int l, r; cin >> l >> r;

        cout << like2017.at(r) - like2017.at(l-1) << endl;

    }

}


// Faster C++ solution for the same problem (measured speedup: 1.5193566767769806x):
#include <bits/stdc++.h>

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

#define rrep(i,n,m) for(int i=((int)(n)-1);i>=m;i--)

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

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

typedef long long ll;

const int INF = 1e9;

const int MOD = 1e9+7;

const ll LINF = 1e18;

using namespace std;

int main(){

    vector<bool> isprime(100010,true);

    isprime[0]=false;

    isprime[1]=false;

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

        if(isprime[i]){

            for(int j=2;i*j<=100000;j++) isprime[i*j]=false;

        }

    }

    

    vector<int> sum(100010,0);

    rep(i,1,100001){

        sum[i]=sum[i-1]+(i%2==1 && isprime[i] && isprime[(i+1)/2]);

    }

    

    int q;

    cin>>q;

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

    rep(i,0,q) cin>>l[i]>>r[i];

    

    rep(i,0,q){

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

    }

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

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

#define REPR(i, n) for(int i = n; i >= 0; i--)

#define FOR(i, m, n) for(int i = m; i < n; i++)

#define INF 1e9

#define ALL(v) v.begin(), v.end()

typedef long long ll;

#define downque(que)  priority_queue<ll> que;

#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;





int main(){

   int q; cin>>q;

   

   bool b[100000+1];

   int kyo[100001]; //kyo[i]=i－１までの2017に似てる数を保存

   



   REP(i,100001){

      b[i]=true;

      kyo[i]=0;

   }

   b[0]=false;

   b[1]=false;



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

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

         b[j]=false;



      }

    }//ふるいにかける



   REP(j,100000){

   int a=(j+1)/2;

   if(j%2==1&&b[j]&&b[a])kyo[j+1]=kyo[j]+1;

   else{kyo[j+1]=kyo[j];}

	

  }

  //累積わ



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

      int l,r; cin>>l>>r;

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

    

   }

  

}

// Faster C++ solution for the same problem (measured speedup: 1.2738227439790821x):
#include <bits/stdc++.h>

using namespace std;

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

#define REPR(i, n) for (int i = n; i >= 0; i--)

#define FOR(i, m, n) for (int i = m; i < n; i++)

#define INF 1e9

#define ALL(v) v.begin(), v.end()

typedef long long ll;

#define downque(que) priority_queue<ll> que;

#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;



int main()

{

    //input

    int q;

    cin >> q;



    //search brothers of 2017



    int max_r = 1e5 + 1;

    

    //素数かどうかの判定表

    vector<bool> Prime(max_r, 1);

    //１からiまでの2017に似てる素数の個数を保存（累積和）

    vector<int> Sum(max_r, 0);



    //１．素数かどうか判定表を作成

    //2.それを用いて、NとN+1/2が素数な数字の個数を数える



    //１．素数かどうか判定表を作成

    Prime[0] = false;

    Prime[1] = false;



    //合成数（素数ではない）を見つけていく

    for (int i = 2; i * i <= max_r; i++)

    {

        //iの倍数を消す

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

        {

            Prime[j] = false;

        }

    }



    //2.Primeを用いて、NとN+1/2が素数な数字の個数を数える

    REP(i, max_r)

    {

        int a = (i + 1) / 2;

        if (Prime[i] && Prime[a])

            Sum[i + 1] = Sum[i] + 1;

        else

        {

            Sum[i + 1] = Sum[i];

        }

    }



    //output

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

    {

        int l, r;

        cin >> l >> r;

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

    }

}
// Slower C++ solution:
#include <iostream>



using namespace std;



int Q;

int lr[100000][2];

int plike[100001];

int p[100001];



int main(){

  cin >> Q;

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

    cin >> lr[i][0] >> lr[i][1];

  }

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

    p[i] = -1;

    plike[i] = 0;

  }

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

    if(p[i] != -1) continue;

    p[i] = i;

    for(int j=i*2;j<100001;j+=i) p[j] = i;

  }

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

    if(i%2 == 0){

      plike[i] = plike[i-1];

      continue;

    }

    if(p[i] != i){

      plike[i] = plike[i-1];

      continue;

    }

    if(p[(i+1)/2] != (i+1)/2){

      plike[i] = plike[i-1];

      continue;

    }

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

  }

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

    cout << plike[lr[i][1]] - plike[lr[i][0]-1] << endl;

  }

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1366559770203637x):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



int p[100001];

ll Q;

ll l[100001];

ll r[100001];

int ans[100001];



int main(){

    ll Q;

    cin >> Q;

    ll N = 100000;

    for(int i=0;i<Q;i++) cin >> l[i] >> r[i];

    for(int i=1;i<=N;i++) p[i] = 1;

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

        if(p[i] != 1) continue;

        for(int j=2;i*j<=N;j++) p[i*j]++;

    }

    p[1] = 0;

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

        if(i%2 == 0){

            ans[i] = 0;

            continue;

        }

        if(p[i] == 1 && p[(i+1)/2] == 1) ans[i] = 1;

        else ans[i] = 0;

    }

    for(int i=2;i<=N;i++) ans[i] += ans[i-1];

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

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

    }

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



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

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

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

#define all2(a, b) (a).begin(), (a).begin() + (b)

#define debug(vari) cerr << #vari << " = " << (vari) << endl;



int main()

{

    int MAX = 100100;

    vector<int> prime(MAX, 1);

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

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

    {

        if (!prime[i])

            continue;

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

        {

            prime[j] = 0;

        }

    }



    vector<int> a(MAX, 0);

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

    {

        if (i % 2 == 0)

            continue;

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

            a[i] = 1;

    }



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

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

    {

        cum[i + 1] = cum[i] + a[i];

    }



    int Q;

    cin >> Q;

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

    {

        int l, r;

        cin >> l >> r;

        r++;

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

    }



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8250381577839812x):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



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

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

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

#define all2(a, b) (a).begin(), (a).begin() + (b)

#define debug(vari) cerr << #vari << " = " << (vari) << endl;



const int INF = 1001001001;



int ck(int a)

{

    if (a == 1)

    {

        return 0;

    }

    for (int i = 2; i * i <= a; i++)

    {

        if (a % i == 0)

        {

            return 0;

        }

    }

    return 1;

}



int main()

{

    int q;

    cin >> q;



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

    rep(i, q) cin >> l[i] >> r[i];

    int r_max = -INF;

    rep(i, q) r_max = max(r_max, r[i]);



    vector<int> tmp(100000 + 10, 0), s(100000 + 10, 0);

    rep(num, r_max + 1)

    {

        if (num % 2 == 0)

            continue;

        if (ck(num) && ck((num + 1) / 2))

        {

            tmp[num]++;

        }

    }

    // rep(i, tmp.size())

    // {

    //     if (0 <= i && i <= r_max)

    //     {

    //         cout << tmp[i] << ' ';

    //     }

    // }

    // cout << endl;



    rep(i, s.size())

    {

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

    }



    // rep(i, s.size())

    // {

    //     if (0 <= i && i <= r_max)

    //     {

    //         cout << s[i] << ' ';

    //     }

    // }

    // cout << endl;



    rep(i, q)

    {

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

    }



    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int p[100009],f[100009];

main()

{

    p[1]=1;



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

    {

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

            p[j]=1;

    }

    p[2]=0;

    for (int i=1; i<=100000; i++)//构造前缀和

    {

        if(p[i]==0 && p[(i+1)/2]==0 && i!=2)//如果该数满足要求，前缀和加1；否则不变

            {

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

            }

        else f[i]=f[i-1];

    }

    int q;

    cin>>q;

    while(q--)

    {

        int l,r;

        cin>>l>>r;

        cout<<f[r]-f[l-1]<<endl;//对于每组询问，直接输出f[r]-f[l-1]

    }

}

// Faster C++ solution for the same problem (measured speedup: 2.1843206809469624x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9+7;

double pi = acos(-1);

int a[100005];

int sum[100005];

void A() {

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

    if (a[i] == 0)

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

        a[j] = 1;

  }

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

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

    if (!a[i] && !a[(i+1)/2] && (i+1) % 2 == 0) sum[i]++; 

  }

}

int main() {

  A();

  int n;

  scanf("%d", &n);

  while (n--) {

    int l, r;

    scanf("%d%d", &l, &r);

    printf("%d\n", sum[r]-sum[l-1]);

  }

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int p[100009],f[100009];

main()

{

    p[1]=1;



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

    {

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

            p[j]=1;

    }

    p[2]=0;

    for (int i=1; i<=100000; i++)//构造前缀和

    {

        if(p[i]==0 && p[(i+1)/2]==0 && i!=2)//如果该数满足要求，前缀和加1；否则不变

            {

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

            }

        else f[i]=f[i-1];

    }

    int q;

    cin>>q;

    while(q--)

    {

        int l,r;

        cin>>l>>r;

        cout<<f[r]-f[l-1]<<endl;//对于每组询问，直接输出f[r]-f[l-1]

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.6753009719828138x):
#include<iostream>

#include<cstring>

using namespace std;

bool isprim[100050];

int prim[100050], f[100050];

void Set(int n){

  int ans = 0;

  memset(isprim, 1, sizeof(isprim));

  memset(prim, 0, sizeof(prim));

  isprim[0] = 0;

  isprim[1] = 0;

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

    if(isprim[i]){

      prim[++ans] = i;

    }

    for(int j = 1; j <= ans && i*prim[j]<=n; j++){

      isprim[i*prim[j]] = 0;

      if(i % prim[j] == 0){

        break;

      }

    }

  }

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

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

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

    }else{

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

    }

  }

}

int main(){

  int q;

  cin>>q;

  Set(100050);

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

    int x, y;

    cin>>x>>y;

    cout<<f[y]-f[x-1]<<endl;

  }

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n[N], m[N];

int main()

{

	int i, j, num = 0, find[N];

	n[1] = 1;

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

	{

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

			n[j] = 1;

	}

	n[2] = 0;

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

	{

		if (n[i] == 0 && n[(i + 1) / 2] == 0)

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

		else

			m[i] = m[i - 1];

	}

	int a, b, c;

	cin >> a;

	for (i = 1; i <= a; i++)

	{

		cin >> b >> c;

		find[i] = m[c] - m[b-1];

	}

	for (i = 1; i <= a; i++)

		cout << find[i] << endl;

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.6749706352749245x):
#include<iostream>

#include<cstring>

using namespace std;

bool isprim[100050];

int prim[100050], f[100050];

void Set(int n){

  int ans = 0;

  memset(isprim, 1, sizeof(isprim));

  memset(prim, 0, sizeof(prim));

  isprim[0] = 0;

  isprim[1] = 0;

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

    if(isprim[i]){

      prim[++ans] = i;

    }

    for(int j = 1; j <= ans && i*prim[j]<=n; j++){

      isprim[i*prim[j]] = 0;

      if(i % prim[j] == 0){

        break;

      }

    }

  }

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

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

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

    }else{

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

    }

  }

}

int main(){

  int q;

  cin>>q;

  Set(100050);

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

    int x, y;

    cin>>x>>y;

    cout<<f[y]-f[x-1]<<endl;

  }

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int p[100009],f[100009];

main()

{

    p[1]=1;



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

    {

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

            p[j]=1;

    }

    p[2]=0;

    for (int i=1; i<=100000; i++)//构造前缀和

    {

        if(p[i]==0 && p[(i+1)/2]==0 && i!=2)//如果该数满足要求，前缀和加1；否则不变

            {

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

            }

        else f[i]=f[i-1];

    }

    int q;

    cin>>q;

    while(q--)

    {

        int l,r;

        cin>>l>>r;

        cout<<f[r]-f[l-1]<<endl;//对于每组询问，直接输出f[r]-f[l-1]

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.5813523656617796x):
#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<string.h>

#include<cmath>

#include<algorithm>

using namespace std;

typedef unsigned long long ull;

#define ll long long

#define INF  0x7fffffff

#define M 200000

#define N 100000

#define legal(x) ((1<=(x))&&((x)<=M))

const ll  mod=1e9 + 7;

ll n,k,ans[M],p[M],t,l,r,f[M],sum;

int main(void){

	p[1] = 1;

	for(ll i = 2;i <= N;i++){

		if(!p[i])

		ans[++sum] = i;

		for(ll j = 1;j <=sum&&i*ans[j]<=N;j++){

			p[ans[j]*i] = 1;

			if(i %ans[j]==0)

			break;

		}

	}

	p[2] = 0;

	for(ll i = 1;i <= N;i++){

		if(p[i]==0&&p[(i+1)/2]==0&&i!=2){

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

		}

		else

		f[i] = f[i-1];

	}

	cin>>t;

	while(t--){

		cin>>l>>r;

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

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n[N], m[N];

int main()

{

	int i, j, num = 0, find[N];

	n[1] = 1;

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

	{

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

			n[j] = 1;

	}

	n[2] = 0;

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

	{

		if (n[i] == 0 && n[(i + 1) / 2] == 0)

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

		else

			m[i] = m[i - 1];

	}

	int a, b, c;

	cin >> a;

	for (i = 1; i <= a; i++)

	{

		cin >> b >> c;

		find[i] = m[c] - m[b-1];

	}

	for (i = 1; i <= a; i++)

		cout << find[i] << endl;

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.5810405537884376x):
#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<string.h>

#include<cmath>

#include<algorithm>

using namespace std;

typedef unsigned long long ull;

#define ll long long

#define INF  0x7fffffff

#define M 200000

#define N 100000

#define legal(x) ((1<=(x))&&((x)<=M))

const ll  mod=1e9 + 7;

ll n,k,ans[M],p[M],t,l,r,f[M],sum;

int main(void){

	p[1] = 1;

	for(ll i = 2;i <= N;i++){

		if(!p[i])

		ans[++sum] = i;

		for(ll j = 1;j <=sum&&i*ans[j]<=N;j++){

			p[ans[j]*i] = 1;

			if(i %ans[j]==0)

			break;

		}

	}

	p[2] = 0;

	for(ll i = 1;i <= N;i++){

		if(p[i]==0&&p[(i+1)/2]==0&&i!=2){

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

		}

		else

		f[i] = f[i-1];

	}

	cin>>t;

	while(t--){

		cin>>l>>r;

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

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int p[100009],f[100009];

main()

{

    p[1]=1;



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

    {

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

            p[j]=1;

    }

    p[2]=0;

    for (int i=1; i<=100000; i++)//构造前缀和

    {

        if(p[i]==0 && p[(i+1)/2]==0 && i!=2)//如果该数满足要求，前缀和加1；否则不变

            {

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

            }

        else f[i]=f[i-1];

    }

    int q;

    cin>>q;

    while(q--)

    {

        int l,r;

        cin>>l>>r;

        cout<<f[r]-f[l-1]<<endl;//对于每组询问，直接输出f[r]-f[l-1]

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.7366706532715268x):
#include<iostream>

#include<iomanip>

#include<cstring>

#include<cstdio>

#include<cmath> 

using namespace std;

long long n[50050],f[100050],zs,a,lefts,rights;

//n[]为辅助空间，里面处理完全是质数；f[]用来前缀和，zs代表质数个数（欧拉线筛需要）

bool b[100050];

//标准的质数表

int main()

{

	b[0]=1,b[1]=1;//初始值

	for(int s=2;s<=100005;s++)//欧拉线筛

	{

		if(!b[s])//一个质数

		{

			n[zs++]=s;

		}

		for(int v=0;v<zs;v++)//处理

		{

			if(s*n[v]>100005)break;//超过了所求的质数范围

			b[n[v]*s]=true;//筛质数

			if(s%n[v]==0)break;//压成到O(n)的关键

		}

	}

	cin>>a;

	for(int s=2;s<=100005;s++)//前缀和

	{

		if(s%2==1&&b[s]==0&&b[(s+1)/2]==0)

		f[s]=1;

		f[s]+=f[s-1];

	}

	while(a--)//输入

	{

		cin>>lefts>>rights;

		cout<<f[rights]-f[lefts-1]<<endl;//前缀和的大法

	}

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n[N], m[N];

int main()

{

	int i, j, num = 0, find[N];

	n[1] = 1;

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

	{

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

			n[j] = 1;

	}

	n[2] = 0;

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

	{

		if (n[i] == 0 && n[(i + 1) / 2] == 0)

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

		else

			m[i] = m[i - 1];

	}

	int a, b, c;

	cin >> a;

	for (i = 1; i <= a; i++)

	{

		cin >> b >> c;

		find[i] = m[c] - m[b-1];

	}

	for (i = 1; i <= a; i++)

		cout << find[i] << endl;

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.7363282156582955x):
#include<iostream>

#include<iomanip>

#include<cstring>

#include<cstdio>

#include<cmath> 

using namespace std;

long long n[50050],f[100050],zs,a,lefts,rights;

//n[]为辅助空间，里面处理完全是质数；f[]用来前缀和，zs代表质数个数（欧拉线筛需要）

bool b[100050];

//标准的质数表

int main()

{

	b[0]=1,b[1]=1;//初始值

	for(int s=2;s<=100005;s++)//欧拉线筛

	{

		if(!b[s])//一个质数

		{

			n[zs++]=s;

		}

		for(int v=0;v<zs;v++)//处理

		{

			if(s*n[v]>100005)break;//超过了所求的质数范围

			b[n[v]*s]=true;//筛质数

			if(s%n[v]==0)break;//压成到O(n)的关键

		}

	}

	cin>>a;

	for(int s=2;s<=100005;s++)//前缀和

	{

		if(s%2==1&&b[s]==0&&b[(s+1)/2]==0)

		f[s]=1;

		f[s]+=f[s-1];

	}

	while(a--)//输入

	{

		cin>>lefts>>rights;

		cout<<f[rights]-f[lefts-1]<<endl;//前缀和的大法

	}

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<string.h>

#include<cmath>

#include<algorithm>

using namespace std;

typedef unsigned long long ull;

#define ll long long

#define INF  0x7fffffff

#define M 200000

#define N 100000

#define legal(x) ((1<=(x))&&((x)<=M))

const ll  mod=1e9 + 7;

ll n,k,ans[M],p[M],t,l,r,f[M],sum;

int main(void){

	p[1] = 1;

	for(ll i = 2;i <= N;i++){

		if(!p[i])

		ans[++sum] = i;

		for(ll j = 1;j <=sum&&i*ans[j]<=N;j++){

			p[ans[j]*i] = 1;

			if(i %ans[j]==0)

			break;

		}

	}

	p[2] = 0;

	for(ll i = 1;i <= N;i++){

		if(p[i]==0&&p[(i+1)/2]==0&&i!=2){

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

		}

		else

		f[i] = f[i-1];

	}

	cin>>t;

	while(t--){

		cin>>l>>r;

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

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.0982186456240877x):
#include<iostream>

#include<iomanip>

#include<cstring>

#include<cstdio>

#include<cmath> 

using namespace std;

long long n[50050],f[100050],zs,a,lefts,rights;

//n[]为辅助空间，里面处理完全是质数；f[]用来前缀和，zs代表质数个数（欧拉线筛需要）

bool b[100050];

//标准的质数表

int main()

{

	b[0]=1,b[1]=1;//初始值

	for(int s=2;s<=100005;s++)//欧拉线筛

	{

		if(!b[s])//一个质数

		{

			n[zs++]=s;

		}

		for(int v=0;v<zs;v++)//处理

		{

			if(s*n[v]>100005)break;//超过了所求的质数范围

			b[n[v]*s]=true;//筛质数

			if(s%n[v]==0)break;//压成到O(n)的关键

		}

	}

	cin>>a;

	for(int s=2;s<=100005;s++)//前缀和

	{

		if(s%2==1&&b[s]==0&&b[(s+1)/2]==0)

		f[s]=1;

		f[s]+=f[s-1];

	}

	while(a--)//输入

	{

		cin>>lefts>>rights;

		cout<<f[rights]-f[lefts-1]<<endl;//前缀和的大法

	}

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



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;

        }

    }



    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 i=0; i<q; i++){

        int l, r;

        cin >> l >> r;

        r++;



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

    }



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1190135327774675x):
#include <bits/stdc++.h>

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

#define chmin(x,y) x = min(x,y)

#define chmax(x,y) x = max(x,y)

using namespace std;

using Graph = vector<vector<int>>;

typedef long long ll;

typedef pair<int, int> P;

const int inf = INT_MAX;

const ll INF = 1LL << 60;

const ll mod = 1e9+7;

const int dx[4] = {-1, 0, 1, 0};

const int dy[4] = {0, -1, 0, 1};



// 084d



int main(){

    int q;

    cin >> q;

    int l[100005], r[100005];

    rep(i, q) cin >> l[i] >> r[i];



    vector<int> c(100005, 1);

    c[0] = 0, c[1] = 0;

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

        if (!c[i]) continue;

        for(int j=i*2; j<100005; j+=i) c[j] = 0;

    }

    vector<int> judge(100005, 1);

    rep(i, 100004){

        if (c[i]==1 and c[(i+1)/2]==1 and i%2==1){

            judge[i] = 1;

        }else judge[i] = 0;

    }

    rep(i, 100004) judge[i+1] = judge[i] + judge[i+1];

    rep(i, q){ 

        int ll = l[i], rr = r[i];

        cout << judge[rr] - judge[ll-1] << endl;

    }

    return 0;

}