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

using namespace std;



bool x[100001];

int q,l[100001],r[100001],ans[100001];



void sh()

{

	int i,j;

	x[0]=1;x[1]=1;

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

	{

		if(x[i]==0)

		{

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

	        {

	        	x[j]=1;

            }

		}

	}  

}



void sh2()

{

	int i;

	for(i=99999;i>=3;i-=2)

	{

		if(x[i]==0)

		{

			if(x[(i+1)/2]!=0)x[i]=1;

		}

	}

	

}



void sh3()

{

	int i;

	ans[3]=1;

	for(i=4;i<=99999;i++)

	{

		if(x[i]==0)ans[i]=ans[i-1]+1;

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

	}	

}



int main()

{

	cin>>q;

	sh();sh2();sh3();

	int i,j;

	for(i=1;i<=q;i++)cin>>l[i]>>r[i];

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

	{

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

	}

}

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

using namespace std;

char a[100000+1];//0表是

int L,r,c[100001];

void prime(){

	a[0]=a[1] = 1;

	int t=sqrt(100000);					

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

		if(a[i]==0) {

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

			     a[j] = 1;	

		}				

	}

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

    {

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

        {

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

        }

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

    }

}

int main(){

	prime(); 						 

	int q;//输入q组数据 

	cin>>q;							

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

		cin>>L>>r;

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

	}	

	return 0;

} 

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

using namespace std;

const int maxn = 1e5+5;

int m,li,ri;

int prime[maxn];

int dp[maxn];

void caculatePrime(){

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

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

		if(!prime[i]){

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

			prime[j] = 1;

		}

	}

}

void caculateNumber(){

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

		dp[i] = (!prime[i] && !prime[(i+1)/2]) ? dp[i-1] + 1 : dp[i-1];

	}

}

int main(){

	cin >> m;

	caculatePrime();

	caculateNumber();

	while(m--){

		cin >> li >> ri;

		cout << dp[ri] - dp[li-1] << endl;

	}

	return 0;

}

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

using namespace std;

char a[100000+1];//0表是

int L,r,c[100001];

void prime(){

	a[0]=a[1] = 1;

	int t=sqrt(100000);					

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

		if(a[i]==0) {

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

			     a[j] = 1;	

		}				

	}

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

    {

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

        {

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

        }

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

    }

}

int main(){

	prime(); 						 

	int q;//输入q组数据 

	cin>>q;							

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

		cin>>L>>r;

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

	}	

	return 0;

} 

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

using namespace std;

#define m 100005

int a[m],b[m],d[m],q[m]; 

int main()

  {

    int T,s=0,p=1;

    memset(a,1,sizeof(a));

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

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

        a[j]=0;

    cin>>T;

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

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

    s++;

    q[i]=s;

                        }

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

    cin>>b[i]>>d[i];

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

    cout<<q[d[i]]-q[b[i]-1]<<endl;

    return 0;

  }

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

using namespace std;

char a[100000+1];//0表是

int L,r,c[100001];

void prime(){

	a[0]=a[1] = 1;

	int t=sqrt(100000);					

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

		if(a[i]==0) {

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

			     a[j] = 1;	

		}				

	}

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

    {

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

        {

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

        }

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

    }

}

int main(){

	prime(); 						 

	int q;//输入q组数据 

	cin>>q;							

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

		cin>>L>>r;

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

	}	

	return 0;

} 

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

#include<iostream>

using namespace std;

#define MAX 100001

int n;

int prime[MAX];

int cnt[MAX]={};

void eratos() {

	int j;

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

	//全部primeと設定する

	prime[i] = 1;

	}

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



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

	j = i+i;

	while(j<MAX) {

	if (prime[j]) prime[j] = 0;

	j += i;

	}

	}

	

}



void like() {

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

	{

	if (i%2==1) {	

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

	++cnt[i];

	}

	}

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

	}

}







int main() {

	int q;

	int l,r;

	cin >> q;

	eratos();

	like();

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

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

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

	}



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

	cout << "p "<<prime[i] << endl;

	cout << "c "<<cnt[i] << endl;

	}

*/

	return 0;

}


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

#include<iostream>

using namespace std;

#define MAX 100001

int n;

int prime[MAX];

int cnt[MAX]={};

void eratos() {

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

	//全部primeと設定する

	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;

	}

	}	

	}

}



void like() {

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

	{

	if (i%2==1) {	

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

	++cnt[i];

	}

	}

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

	}

}







int main() {

	int q;

	int l,r;

	cin >> q;

	eratos();

	like();

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

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

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

	}



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

	cout << "p "<<prime[i] << endl;

	cout << "c "<<cnt[i] << endl;

	}

*/

	return 0;

}


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

#include<algorithm>

#include<string>

#include<map>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

typedef long long int llint;

typedef pair<ll, ll> pa;

#define MM 1000000000

#define MOD MM+7

#define MAX 101000

#define MAP 110

#define initial_value -1

#define Pair pair<int,int>

#define chmax(a,b) (a<b ? a=b:0)

#define chmin(a,b) (a>b ? a=b:0)

#define INF (1 << 29) //536870912

const ll DEP = 1e18;

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

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

int Q;

int main(){

    //エラトステネスの篩

    int MAXX = 101010;

    vector<int> is_prime(MAXX,1);

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

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

        if(!is_prime[i]) continue;

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

    }

    //2017-like

    vector<int> a(MAXX,0);

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

        if(i % 2 == 0) continue;

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

    }

    //累積和

    vector<int> s(MAXX,0);

    for(int i = 0; i < MAXX; i++) s[i+1] = s[i]+a[i];

    //クエリ

    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<iostream>

#include<algorithm>

#include<string>

#include<map>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

typedef long long int llint;

typedef pair<ll, ll> pa;

#define MM 1000000000

#define MOD MM+7

#define MAX 101000

#define MAP 110

#define initial_value -1

#define MAX_T 1001

#define Pair pair<int,int>

#define chmax(a,b) (a<b ? a=b:0)

#define chmin(a,b) (a>b ? a=b:0)

#define INF (1 << 29) //536870912

const ll DEP = 1e18;

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

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

int main(){

    vector<bool> pr(100001,true);

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

        if(pr[i]){

            for(ll j = i*i; j <= 100000; j += i){

                pr[j] = false;

            }

        }

    }

    vector<int> ans(100001,0);

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

        if(i % 2 == 1 && pr[i] && pr[(i+1)/2]) ans[i] = ans[i-1] + 1;

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

    }

    int q; cin >> q;

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

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

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

    }

    return 0;

}


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

using namespace std;

#define loop(i,L,R) for(int i=(L);i<=(R);i++)

#define rept(i,L,R) for(int i=(L);i<(R);i++)

#define isc(n) scanf("%d",&n)

#define llsc(n) scanf("%lld",&n)

#define dsc(n) scanf("%lf",&n)

#define enl cout<<endl

#define pb(x) push_back(x)

#define xx first

#define yy second

typedef long long ll;

typedef pair<int,int>PI;

typedef pair<pair<int,int>,int>PII;

const int mx=1e5+10;

int arr[mx],prime[mx],cum[mx];

int main()

{

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

	{

        if(arr[i]==0)

        {

            prime[i]=1;

            for(int j=i*2;j<mx;j+=i)arr[j]=1;

        }

	}

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

	{

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

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

       // if(i<100)cout<<i<<" "<<cum[i]<<endl;

    }

    int n,l,r;

    cin>>n;

    while(n--)

    {

        cin>>l>>r;

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

    }

	return 0;

}


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



using namespace std;



#define td typedef

td long long ll;



ll in()

{

    ll a;

    scanf("%lld",&a);

    return a;

}



bool prime[100005];

int chumu[100005];



int main()

{

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

    for(ll i=2;i<=100003;i++)

    {

        if(!prime[i])

        {

            for(ll j=i*i;j<=100003;j+=i)

                prime[j]=1;

        }

    }

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

    {

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

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

        else

            chumu[i]=chumu[i-1];

    }

    int t=in();

    while(t--)

    {

        int x=in(),y=in();

        printf("%d\n",chumu[y]-chumu[x-1]);

    }

}


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

using namespace std;



int dp[100009], total[100009];

int store[100009], mark[100009], nPrime, isPrime[100009];



///seieve

void seive(int n)

{

    int i,j, lim = sqrt(n*1.0) +2;



    mark[1] = 1;

    for(i = 4; i<=n; i+=2) mark[i] = 1;



    store[nPrime++] = 2;



    isPrime[2] = 1;



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

    {

        if(!mark[i])

        {

            store[nPrime++] = i;

            isPrime[i] = 1;



            if(i<=lim)

            {

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

                {

                    mark[j]=1;

                }

            }

        }

    }





}



int f(int n) /// is like 2017

{

    if(dp[n]!=-1) return dp[n];

    if(n%2==0) return dp[n] = 0;

    if(isPrime[n]==1 && isPrime[ (n+1)/2 ]==1) return dp[n] = 1;

    else return dp[n] = 0;

}



void cnt(int N)

{

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

    total[1] = 0;

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

    {

        total[i] = total[i-1]+dp[i];

    }

}



int main()

{

    int q;

    int l, r;

    int ans = 0;



    seive(100002);

    memset(dp,-1,sizeof(dp));

    cnt(100002);



    //for(int i=0; i<nPrime; i++) cout<<store[i]<<" ";

    //for(int i=0; i<100000; i++) if(dp[i]) cout<<i<<" "<<total[i]<<" "<<endl;



    cin>>q;

    while(q--)

    {

        cin>>l>>r;

        if(l==1) ans = total[r];

        else ans = total[r] - total[l-2];

        cout<<ans<<endl;

    }



    //main();





    return 0;

}


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

using namespace std;



const int N = 1e5 + 100;



int q, l, r, cnt[N];

bool mark[N];



int main() {

	ios::sync_with_stdio(false), cin.tie(0);

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

		if(mark[i] == false) {

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

				mark[j] = true;

		}

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

		cnt[i] = cnt[i - 1] + (mark[i] == false && mark[(i + 1) >> 1] == false);

	cin >> q;

	while(q--) {

		cin >> l >> r;

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

	}

	return 0;

}


// 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 + 100;



int q, l, r, cnt[N];

bool mark[N];



int main() {

	ios::sync_with_stdio(false), cin.tie(0);

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

		if(mark[i] == false) {

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

				mark[j] = true;

		}

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

		cnt[i] = cnt[i - 1] + (mark[i] == false && mark[(i + 1) >> 1] == false);

	cin >> q;

	while(q--) {

		cin >> l >> r;

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

	}

	return 0;

}


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

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int INF = 1e9;

const ll LINF = 1e18;



/*

<url:https://abc084.contest.atcoder.jp/tasks/abc084_d>

問題文============================================================

 「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。

 

 Q 個のクエリが与えられます。

 

 クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、

 li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。

=================================================================



解説=============================================================



 1..N までに2017素数であるものの個数を累積和で確保しておき

 一つのキューに対して O(1) でもとまる

 

================================================================

*/

const ll MAX_PRIME = 100000;

vector<int> primes(MAX_PRIME + 1);

vector<int> is_prime(MAX_PRIME + 1,true);

vector<int> prime2017(MAX_PRIME + 1,0);

vector<int> cusum(MAX_PRIME + 1,0);

void init_primes(){

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

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

        if(is_prime[i]){

            primes.push_back(i);

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

        }

    }

}



void init(){

    init_primes();

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

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

            prime2017[i] = true;

        }

    }

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

        cusum[i+1] = cusum[i] + prime2017[i+1];

    }

}

int main(void) {

	cin.tie(0); ios::sync_with_stdio(false);

    init();

    ll Q; cin >> Q;

    while(Q--){

        ll l,r; cin >> l >> r;

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

    }

	return 0;

}


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

using namespace std;



const int N = 1e5 + 100;



int q, l, r, cnt[N];

bool mark[N];



int main() {

	ios::sync_with_stdio(false), cin.tie(0);

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

		if(mark[i] == false) {

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

				mark[j] = true;

		}

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

		cnt[i] = cnt[i - 1] + (mark[i] == false && mark[(i + 1) >> 1] == false);

	cin >> q;

	while(q--) {

		cin >> l >> r;

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

	}

	return 0;

}


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

#include <iostream>

#include <vector>

using namespace std;



typedef long long ll;



const int MAX_N = 1e5 + 5;;

int lp[MAX_N];

int pr[MAX_N];

int ind;

int psum[MAX_N];



int main() {

	ios::sync_with_stdio(false), cin.tie(0);

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

		if (lp[i] == 0) {

			lp[i] = i;

			pr[ind++] = i;

		}



		for (int j = 0; j < ind && pr[j] <= lp[i] && i * pr[j] < MAX_N; j++)

			lp[i * pr[j]] = pr[j];

	}



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

		psum[i] = psum[i - 1];

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

			psum[i]++;

	}



	int q;

	cin >> q;



	while (q--) {

		int l, r;

		cin >> l >> r;

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

	}

	return 0;

}

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

using namespace std;



const int N = 1e5 + 100;



int q, l, r, cnt[N];

bool mark[N];



int main() {

	ios::sync_with_stdio(false), cin.tie(0);

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

		if(mark[i] == false) {

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

				mark[j] = true;

		}

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

		cnt[i] = cnt[i - 1] + (mark[i] == false && mark[(i + 1) >> 1] == false);

	cin >> q;

	while(q--) {

		cin >> l >> r;

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

	}

	return 0;

}


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

using namespace std;

int dis[100009],vis[100009],n,l,r;

int main()

{

    dis[1]=1;

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

    {

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

            dis[j]=1;

    }

    dis[2]=0;

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

    {

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

        {

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

        }

        else 

        {

            vis[i]=vis[i-1];

        }

    }

    cin>>n;

    while(n--)

    {

        cin>>l>>r;

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

    }

}

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

bool f[100001];

int c[100002];

int N, L, R;

int main ()

{

    for(int i =2; 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];

    scanf ("%d" ,&N);

    while (N--)

    {

        scanf ("%d %d " ,&L ,& R );

        printf ("%d \n " , c[R] - c[L-1]);

    }

}


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

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;

}

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

bool f[100001];

int c[100002];

int N, L, R;

int main ()

{

    for(int i =2; 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];

    scanf ("%d" ,&N);

    while (N--)

    {

        scanf ("%d %d " ,&L ,& R );

        printf ("%d \n " , c[R] - c[L-1]);

    }

}


// 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 <cstring>

using namespace std;



bool prime[200000];

int s[200000];



int main()

{

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

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

	

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

	{

		if(prime[i])

		{

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

			{

				prime[j] = 0;

			}

		}

	}

	

	for(int i=1; i<150000; i+=2)

	{

		if(prime[i])

		{

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

			{

				s[i] = 1;

			}

			

		}

	}

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

	{

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

	}

	

	

	int q;

	cin >> q;

	int a, b;

	

	while(q--)

	{

		cin >> a >> b;

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

	}

	

	

	return 0;

}

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

}

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

bool f[100001];

int c[100002];

int N, L, R;

int main ()

{

    for(int i =2; 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];

    scanf ("%d" ,&N);

    while (N--)

    {

        scanf ("%d %d " ,&L ,& R );

        printf ("%d \n " , c[R] - c[L-1]);

    }

}


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

using namespace std;

const int N = 100010;

int prime[N],sum[N];

int q,l,r;



void init()

{

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

		prime[i]=1;

}

void find()

{

	init();

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

		if(prime[i])

		{

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

				prime[j]=0;

		}

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

		if(prime[i]&&prime[(i+1)/2]) sum[i]=sum[i-1]+1;

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

}

int main()

{

	cin>>q;

	find();

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

	{

		cin>>l>>r;

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

	}

}

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

bool f[100001];

int c[100002];

int N, L, R;

int main ()

{

    for(int i =2; 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];

    scanf ("%d" ,&N);

    while (N--)

    {

        scanf ("%d %d " ,&L ,& R );

        printf ("%d \n " , c[R] - c[L-1]);

    }

}


// Fastest known solution for this problem: