stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#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

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

bool prime[233333];

void makeprime(int n){

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

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

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

        if(prime[i]){

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

                prime[i*j]=0;

            }

        }

    }

}

int f[233333];

int main(){

	int T;

	cin>>T;

	makeprime(100010);

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

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

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

		}

		else{

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

		}

	}

	while(T--){

		int l,r,ans=0;

		cin>>l>>r;

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

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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]

    }

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

bool prime[233333];

void makeprime(int n){

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

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

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

        if(prime[i]){

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

                prime[i*j]=0;

            }

        }

    }

}

int f[233333];

int main(){

	int T;

	cin>>T;

	makeprime(100010);

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

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

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

		}

		else{

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

		}

	}

	while(T--){

		int l,r,ans=0;

		cin>>l>>r;

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

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

		}

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

	}

}

// Optimized solution to the same problem (faster):
#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;

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

	}

}

// Optimized solution to the same problem (faster):
#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;

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

    }

}


// Optimized solution to the same problem (faster):
#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;

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

    

   }

  

}

// Optimized solution to the same problem (faster):
#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;

    }

}


// Fastest known solution for this problem: