stablegradients/pie-gem5-pairs huggingface dataset:
// 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.955798776284191x):
#include<iostream>

#include<string.h>

using namespace std;

#define N 100001



int arr[N];

int res[N];



void screenPrime(){

	memset(arr, 0, sizeof(arr));

	//埃氏筛素数 

	arr[0] = arr[1] = 1;

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

		if(!arr[i]){

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

				arr[i*j] = 1;

			}

		}

	}

	//构造前缀和

	res[0] = 0;

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

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

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

		}else{

			res[i] = res[i-1];

		}

	}

	 

}





int main(){

	screenPrime();

	int t, m, n;

	cin >> t;

	while(t--){

		int count = 0;

		cin >> m >> n;

		cout << res[n]-res[m-1] << endl;

	}

	return 0;

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

#include<cstdio>

#include<cstdlib>

#include<cstring>

#define maxn 100005

using namespace std;

int p[maxn];

int vis[maxn];

int sum[maxn];

int t;

int main()

{

	

	int i,j,q,l,r;

	memset(sum,0,sizeof(sum));

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

	{

		if(!vis[i]) p[++t]=i;

		for(j=1;j<=t&&i*p[j]<=100000;j++)

		{

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

			if(i%p[j]==0) break;

			

		}

	}

	scanf("%d",&q);

	sum[1]=0;sum[2]=0;

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

	{

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

		{

			sum[i]++;

		}

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

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

		//printf("%d %d\n",i,sum[i]);

	}

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

	{

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

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

	}

	return 0;

}

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

using namespace std;

int p[100010],f[100010];

#define N 100000

int main(){

p[0]=p[1]=1;

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

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

if(!p[j])p[j]=1;

}

}

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

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

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

}

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

}

int n;

cin>>n;

while(n--){

int l,r;

cin>>l>>r;

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



}

return 0;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

using namespace std;

#ifndef FAST_IO

 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);

#endif

 

#define FILE_IO freopen("input.txt","r",stdin)

#define int long long

#define f first

#define s second

#define endl '\n'

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

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

 

const int MOD = 1e9 + 7;

const int INF = 1e18;

 

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T>void print(T t){for(auto &it:t)cout<<it<<" ";}

inline int powerexp(int a,int b,int m = MOD){int res=1;while(b){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res%m;}

inline int modinv(int a){return powerexp(a,MOD-2,MOD);}

inline int lcm(int a,int b){int g=__gcd(a,b);return a/g*b;}

const int N = 2e5 + 1;

bool isprime[N];

int dp[N];

void prime_gen(){

  fill(isprime + 2,isprime + N,true);

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

	  if (isprime[i]){

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

			 isprime[j] = false;  

		   }  

		}

	}	

}

 

void precompute(){

  	prime_gen();

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

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

     }

}

 

void solve(){

   precompute();

   int q;

   cin >> q;

   while (q--){

	   int l, r;

	   cin >> l >> r;

	   int ret = dp[r] - dp[l-1];

	   cout << ret << endl;

	 }

}

int32_t main(){

   IOS;

   solve();

   #ifdef LOCAL_DEFINE

   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;

   #endif

}

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

using namespace std;

int p[100010],f[100010];

#define N 100000

int main(){

p[0]=p[1]=1;

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

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

if(!p[j])p[j]=1;

}

}

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

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

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

}

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

}

int n;

cin>>n;

while(n--){

int l,r;

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: 2.5002755268136845x):
#include<bits/stdc++.h>

using namespace std;

int p[100010],f[100010];

#define N 100000

int main(){

p[0]=p[1]=1;

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

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

if(!p[j])p[j]=1;

}

}

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

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

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

}

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

}

int n;

cin>>n;

while(n--){

int l,r;

cin>>l>>r;

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



}

return 0;

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

#include<string.h>

using namespace std;

#define N 100001



int arr[N];

int res[N];



void screenPrime(){

	memset(arr, 0, sizeof(arr));

	//埃氏筛素数 

	arr[0] = arr[1] = 1;

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

		if(!arr[i]){

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

				arr[i*j] = 1;

			}

		}

	}

	//构造前缀和

	res[0] = 0;

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

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

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

		}else{

			res[i] = res[i-1];

		}

	}

	 

}





int main(){

	screenPrime();

	int t, m, n;

	cin >> t;

	while(t--){

		int count = 0;

		cin >> m >> n;

		cout << res[n]-res[m-1] << endl;

	}

	return 0;

}

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

using namespace std;

int p[100010],f[100010];

#define N 100000

int main(){

p[0]=p[1]=1;

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

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

if(!p[j])p[j]=1;

}

}

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

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

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

}

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

}

int n;

cin>>n;

while(n--){

int l,r;

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 f[N],n,ans[N],x=0,a,b,temp;

void Check(){

	f[1]=1;

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

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

	f[j]=1;

}

int main(){

	Check();

	ans[1]=0;

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

		if(!f[i]&&!f[(i+1)>>1]){

		ans[i]=temp+1;

		temp=ans[i];

	}

	else

	ans[i]=temp;

	}

		cin>>n;

		while(n--){

			cin>>a>>b;

			if(!f[a]&&!f[(a+1)>>1])

			cout<<(ans[b]-ans[a]+1)<<endl;

			else

			cout<<ans[b]-ans[a]<<endl;

		}

}

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

using namespace std;

int p[100010],f[100010];

#define N 100000

int main(){

p[0]=p[1]=1;

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

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

if(!p[j])p[j]=1;

}

}

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

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

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

}

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

}

int n;

cin>>n;

while(n--){

int l,r;

cin>>l>>r;

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



}

return 0;

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

using namespace std;



const int MAX_N = (int)1e5 + 5;



std::vector<bool> isPrime;



void sieve(int max){

  if(max + 1 > isPrime.size()) {     // resizeで要素数が減らないように

      isPrime.resize(max + 1, true); // isPrimeに必要な要素数を確保

  }

  isPrime[0] = false; // 0は素数ではない

  isPrime[1] = false; // 1は素数ではない



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

    if(isPrime[i]) {

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

        isPrime[i * j] = false;

      }

    }

  }

}



int accumedNumOfPrime[MAX_N];



int q;

int l[MAX_N], r[MAX_N];



int main(void){

  // Here your code !

  scanf("%d\n", &q);

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

    scanf("%d %d", &l[i], &r[i]);

  }



  sieve(MAX_N);



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

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

      accumedNumOfPrime[i] += 1;

    }

  }



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

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

  }



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

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

    scanf("%d %d", &l[i], &r[i]);

  }



  return 0;

}

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

using namespace std;



using ll = long long int;



const int MAX = (int)(1e5 + 5);

const ll INF = (ll)(1e10 + 5);



const int MAX_N = (int)(1e5 + 5);



int q;



bool prime[MAX_N];



int cnt[MAX_N];



void prepare() {

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

    prime[i] = true;

  }



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



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

    prime[i] = false;

  }



  prime[2] = true;



  for (int i = 3; i * i < MAX_N; ++i) {

    if (!prime[i]) continue;



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

      prime[j] = false;

    }

  }



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

    int other = (i + 1) / 2;

    cnt[i] = cnt[i - 1] + (prime[i] && prime[other] ? 1 : 0);

  }



  // for (int i = 0; i < 100; ++i) {

  //   printf("%d: %d\n", i, prime[i]);

  // };



  // for (int i = 0; i < 100; ++i) {

  //   printf("%d: %d\n", i, cnt[i]);

  // };

}



int main(void) {

  // Here your code !

  scanf("%d", &q);



  prepare();



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

    int l, r;

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



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

  }



  return 0;

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

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

#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)

using namespace std;



using ll=long long;



using vi=vector<int>;

using vll=vector<ll>;

using vvi=vector<vi>;



int main() {

  int MAX=pow(10,5)+1;

  vi is_prime(MAX,1);

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

  rep(i,2,MAX) {

    if (is_prime[i]==0) {

      continue;

    }

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

      is_prime[j]=0;

    }

  }

  vi a(MAX,0);

  rep(i,0,MAX) {

    if (i%2==0) {

      continue;

    } else if (is_prime[i] && is_prime[(i+1)/2]) {

      a[i]=1;

    }

  }

  vi s(MAX+1,0);

  rep(i,0,MAX) {

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

  }

  int Q; cin >>Q;

  rep(q,0,Q) {

    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.13055827218473x):
#include <bits/stdc++.h>

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

#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)

using namespace std;



using ll=long long;



using vi=vector<int>;

using vll=vector<ll>;

using vvi=vector<vi>;



int main() {

  int MAX=pow(10,5)+1;

  vi is_prime(MAX,1);

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

  rep(i,2,sqrt(MAX)) {

    if (is_prime[i]==0) {

      continue;

    }

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

      is_prime[j]=0;

    }

  }

  vi a(MAX,0);

  rep(i,0,MAX) {

    if (i%2==0) {

      continue;

    } else if (is_prime[i] && is_prime[(i+1)/2]) {

      a[i]=1;

    }

  }

  vi s(MAX+1,0);

  rep(i,0,MAX) {

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

  }

  int Q; cin >>Q;

  rep(q,0,Q) {

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

    r++;

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

  }

  return 0;

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

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

#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)

using namespace std;



using ll=long long;



using vi=vector<int>;

using vll=vector<ll>;

using vvi=vector<vi>;



int main() {

  int MAX=pow(10,5)+1;

  vi is_prime(MAX,1);

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

  rep(i,2,MAX) {

    if (is_prime[i]==0) {

      continue;

    }

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

      is_prime[j]=0;

    }

  }

  vi a(MAX,0);

  rep(i,0,MAX) {

    if (i%2==0) {

      continue;

    } else if (is_prime[i] && is_prime[(i+1)/2]) {

      a[i]=1;

    }

  }

  vi s(MAX+1,0);

  rep(i,0,MAX) {

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

  }

  int Q; cin >>Q;

  rep(q,0,Q) {

    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.2576468020729668x):
#include <bits/stdc++.h>

#define rep(i,l,r) for(int i=l; i<(int)(r); i++)

#define rep_eq(i,l,r) for(int i=l; i<=(int)(r); i++)

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

using namespace std;



template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



using ll=long long;



using vb=vector<bool>;

using vi=vector<int>;

using vll=vector<ll>;

using vvi=vector<vi>;

using vs=vector<string>;



int main() {

  cin.tie(nullptr);

  ios::sync_with_stdio(false);



  int MAX=101010;

  vb is_prime(MAX, true);

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

  rep(i,2,MAX) {

    if (!is_prime[i]) {continue;}

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

  }



  vi a(MAX);

  rep(i,0,MAX) {

    if (i%2==0) {continue;}

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

  }



  vi s(MAX+1);

  rep(i,0,MAX) {s[i+1]=s[i]+a[i];}



  int Q; cin >>Q;

  rep(q,0,Q) {

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

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

  }



  return 0;

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

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

#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)

using namespace std;



using ll=long long;



using vi=vector<int>;

using vll=vector<ll>;

using vvi=vector<vi>;



int main() {

  int MAX=pow(10,5)+1;

  vi is_prime(MAX,1);

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

  rep(i,2,sqrt(MAX)) {

    if (is_prime[i]==0) {

      continue;

    }

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

      is_prime[j]=0;

    }

  }

  vi a(MAX,0);

  rep(i,0,MAX) {

    if (i%2==0) {

      continue;

    } else if (is_prime[i] && is_prime[(i+1)/2]) {

      a[i]=1;

    }

  }

  vi s(MAX+1,0);

  rep(i,0,MAX) {

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

  }

  int Q; cin >>Q;

  rep(q,0,Q) {

    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.1124121887522405x):
#include <bits/stdc++.h>

#define rep(i,l,r) for(int i=l; i<(int)(r); i++)

#define rep_eq(i,l,r) for(int i=l; i<=(int)(r); i++)

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

using namespace std;



template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



using ll=long long;



using vb=vector<bool>;

using vi=vector<int>;

using vll=vector<ll>;

using vvi=vector<vi>;

using vs=vector<string>;



int main() {

  cin.tie(nullptr);

  ios::sync_with_stdio(false);



  int MAX=101010;

  vb is_prime(MAX, true);

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

  rep(i,2,MAX) {

    if (!is_prime[i]) {continue;}

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

  }



  vi a(MAX);

  rep(i,0,MAX) {

    if (i%2==0) {continue;}

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

  }



  vi s(MAX+1);

  rep(i,0,MAX) {s[i+1]=s[i]+a[i];}



  int Q; cin >>Q;

  rep(q,0,Q) {

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

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

  }



  return 0;

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

using namespace std;



int main(void){

    int q,n = 0;

    cin >> q;

    int l[q],r[q];

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

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

        n = max(n,r[i]);

    }

    

    int is_prime[100005] = {},num[100005] = {};

    

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

        if(!is_prime[i]){

            for(int j = 2*i;j <= 100000;j += i)is_prime[j] = 1;

        }

    }

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

        if(is_prime[i] == 0 && is_prime[(i+1)/2] == 0)num[i] += num[i-1] + 1;

        else num[i] += num[i-1];

    }

    

    for(int i = 0;i < q;i++)cout << num[r[i]]-num[l[i]-1] << endl;

}

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

using namespace std;



int main(void){

    int q,n = 0;

    cin >> q;

    int l[q],r[q];

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

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

        n = max(n,r[i]);

    }

    

    int is_prime[100005] = {},num[100005] = {};

    

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

        if(!is_prime[i]){

            for(int j = 2*i;j <= 100000;j += i)is_prime[j] = 1;

        }

    }

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

        if(is_prime[i] == 0 && is_prime[(i+1)/2] == 0)num[i] += num[i-1] + 1;

        else num[i] += num[i-1];

    }

    

    for(int i = 0;i < q;i++)cout << num[r[i]]-num[l[i]-1] << endl;

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

using namespace std;

using ll = long long;

using vl = vector<ll>;

using vvl = vector<vl>;

using vi = vector<int>;

using vvi = vector<vi>;

#define ote(x) cout<<(x)<<endl

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

#define rp(i,s,e) for(int i=(s);i<(e);++i)

#define rpz(i,e) rp(i,0,e)



using PII = pair<int,int>;



// 素数列挙 (エラトステネスの篩)

vector<bool> primes_create(ll n){

  vector<bool> primes(n+1, true);

	primes[0] = primes[1] = false;

  for(ll i=2L; i*i<=n; ++i){

		ll ix = i + i;

		while(ix <= n){

			primes[ix] = false;

			ix += i;

		}

  }

  return primes;

}



int main(){

	vector<bool> primes = primes_create(100000+1);

	vi C(primes.size());//Cumulative sum

	rp(n, 1, primes.size()) C[n] += C[n-1] + (primes[n] && (n+1)%2==0 && primes[(n+1)/2]);



	// rpz(i,primes.size()){printf("%d\n",C[i]);}puts("");//



	int Q; cin>>Q;

	vi ans(Q);

	rpz(i, Q){

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

		cout<< C[r] - C[l] + (C[l]!=C[l-1]) <<endl;

	}

}

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

using namespace std;



vector<bool> primes_create(int n){

  vector<bool> primes(n+1, true);

	primes[0] = primes[1] = false;

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

		if(primes[i]) for(int j=i+i; j<=n; j+=i) primes[j] = false;

  return primes;

}



int main(){

	vector<bool> primes = primes_create(100000+1);



	vector<int> C(primes.size());//Cumulative sum

	for(int n=1; n<primes.size(); ++n)

		C[n] += C[n-1] + (primes[n] && (n+1)%2==0 && primes[(n+1)/2]);



	int Q; cin>>Q;

	while(Q--){

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

		cout<< C[r] - C[l] + (C[l]!=C[l-1]) <<endl;

	}

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

using namespace std;



vector<bool> primes_create(int n){

  vector<bool> primes(n+1, true);

	primes[0] = primes[1] = false;

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

		int ix = i + i;

		while(ix <= n){

			primes[ix] = false;

			ix += i;

		}

  }

  return primes;

}



int main(){

	vector<bool> primes = primes_create(100000+1);



	vector<int> C(primes.size());//Cumulative sum

	for(int n=1; n<primes.size(); ++n)

		C[n] += C[n-1] + (primes[n] && (n+1)%2==0 && primes[(n+1)/2]);



	int Q; cin>>Q;

	while(Q--){

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

		cout<< C[r] - C[l] + (C[l]!=C[l-1]) <<endl;

	}

}

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

using namespace std;



vector<bool> primes_create(int n){

  vector<bool> primes(n+1, true);

	primes[0] = primes[1] = false;

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

		if(primes[i]) for(int j=i+i; j<=n; j+=i) primes[j] = false;

  return primes;

}



int main(){

	vector<bool> primes = primes_create(100000+1);



	vector<int> C(primes.size());//Cumulative sum

	for(int n=1; n<primes.size(); ++n)

		C[n] += C[n-1] + (primes[n] && (n+1)%2==0 && primes[(n+1)/2]);



	int Q; cin>>Q;

	while(Q--){

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

		cout<< C[r] - C[l] + (C[l]!=C[l-1]) <<endl;

	}

}
// 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.1882261767179185x):
#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;

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[now] ){

      if( (double)now >= sqrt(n) ) return;

      ll cnt = 2;

      while( now*cnt <= n ){

        isPr[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[i] && isPr[(i+1)/2] ){

      ++now;

      sum[i] = now;

    }else{

      sum[i] = now;

    }

  }

  rep(i,q){

    ll l,r;

    cin >> l >> r;

    ll ans;

    if( isPr[l] && isPr[(l+1)/2] ){

      ans = sum[r]-sum[l]+1;

    }else{

      ans = sum[r]-sum[l];

    }

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

  }

  return 0;

}