stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.285567813736868x):
#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;

}
// Slower C++ solution:
#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;

  }

// Faster C++ solution for the same problem (measured speedup: 3.107859199812148x):
#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;

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

using namespace std;

long long s,n,i,j,a,b,o[1000000]= {1,1},k[1000009];

int main() {

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

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

			o[j]=1;

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

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

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

		}

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

	}

	cin>>n;

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

		cin>>a>>b;

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

	}

	return 0;

}

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

#include<time.h>

#define Max 100005

int Arr[Max] = {0};

int Arr2[Max] = {0};

using namespace std;

int main(){

    // int t1, t2;

    // t1 = clock();

    int q, i, j, n, m, ans=0;

    for(i=2; i<Max; i++){

        if(Arr[i] == 0)

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

            Arr[j] = 1;

    }

    for(i=3; i<Max; i++)

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

            Arr2[i] = ++ans;

        else

            Arr2[i] = ans;



    cin>>q;

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

        cin>>n>>m;

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

    }

    // t2 = clock();

    // cout<<t2 - t1<<endl;

    // for(i=0; i<1000; i++){

    //     // if(Arr2[i] == )

    //     cout<<i<<"|"<<Arr2[i]<<"    ";

    // }

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

#include<algorithm>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<iomanip>

#include<vector>

#include<queue>

#include<set>

#include<map>

using namespace std;

int n;

int p[100005],f[100005];

int main()

{

	p[1]=1;

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

    {

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

        p[j]=1;

    }

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

    {

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

		{

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

		}

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

    }

	scanf("%d",&n);

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

	{

		int x,y;

		scanf("%d%d",&x,&y);

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



	}

	return 0;

}

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

#include<time.h>

#define Max 100005

int Arr[Max] = {0};

int Arr2[Max] = {0};

using namespace std;

int main(){

    // int t1, t2;

    // t1 = clock();

    int q, i, j, n, m, ans=0;

    for(i=2; i<Max; i++){

        if(Arr[i] == 0)

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

            Arr[j] = 1;

    }

    for(i=3; i<Max; i++)

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

            Arr2[i] = ++ans;

        else

            Arr2[i] = ans;



    cin>>q;

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

        cin>>n>>m;

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

    }

    // t2 = clock();

    // cout<<t2 - t1<<endl;

    // for(i=0; i<1000; i++){

    //     // if(Arr2[i] == )

    //     cout<<i<<"|"<<Arr2[i]<<"    ";

    // }

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

#include <cstring>



#define SIZE 100005



// 1为2017数

int numbers[SIZE];

int _2017[SIZE];



int main() {

	numbers[1] = 0;

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

		numbers[i] = 1;

	}



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

		if (numbers[i]) {

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

				numbers[j * i] = 0;

			}

		}

	}



	// 求2017数

	memcpy(_2017, numbers, sizeof numbers);

	_2017[2] = 0;

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

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

			_2017[i] = 0;

		}

	}



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

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

	}





	int question;

	std::cin >> question;

	while (question--) {

		int left, right;

		std::cin >> left >> right;



		std::cout << _2017[right] - _2017[left - 1] << std::endl;

	}



	return 0;

}


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

#include<time.h>

#define Max 100005

int Arr[Max] = {0};

int Arr2[Max] = {0};

using namespace std;

int main(){

    // int t1, t2;

    // t1 = clock();

    int q, i, j, n, m, ans=0;

    for(i=2; i<Max; i++){

        if(Arr[i] == 0)

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

            Arr[j] = 1;

    }

    for(i=3; i<Max; i++)

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

            Arr2[i] = ++ans;

        else

            Arr2[i] = ans;



    cin>>q;

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

        cin>>n>>m;

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

    }

    // t2 = clock();

    // cout<<t2 - t1<<endl;

    // for(i=0; i<1000; i++){

    //     // if(Arr2[i] == )

    //     cout<<i<<"|"<<Arr2[i]<<"    ";

    // }

}
// 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: 1.9965620235063237x):
#include<iostream>

#include<time.h>

#define Max 100005

int Arr[Max] = {0};

int Arr2[Max] = {0};

using namespace std;

int main(){

    // int t1, t2;

    // t1 = clock();

    int q, i, j, n, m, ans=0;

    for(i=2; i<Max; i++){

        if(Arr[i] == 0)

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

            Arr[j] = 1;

    }

    for(i=3; i<Max; i++)

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

            Arr2[i] = ++ans;

        else

            Arr2[i] = ans;



    cin>>q;

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

        cin>>n>>m;

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

    }

    // t2 = clock();

    // cout<<t2 - t1<<endl;

    // for(i=0; i<1000; i++){

    //     // if(Arr2[i] == )

    //     cout<<i<<"|"<<Arr2[i]<<"    ";

    // }

}
// Slower C++ solution:
#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;

  }

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

#include<time.h>

#define Max 100005

int Arr[Max] = {0};

int Arr2[Max] = {0};

using namespace std;

int main(){

    // int t1, t2;

    // t1 = clock();

    int q, i, j, n, m, ans=0;

    for(i=2; i<Max; i++){

        if(Arr[i] == 0)

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

            Arr[j] = 1;

    }

    for(i=3; i<Max; i++)

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

            Arr2[i] = ++ans;

        else

            Arr2[i] = ans;



    cin>>q;

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

        cin>>n>>m;

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

    }

    // t2 = clock();

    // cout<<t2 - t1<<endl;

    // for(i=0; i<1000; i++){

    //     // if(Arr2[i] == )

    //     cout<<i<<"|"<<Arr2[i]<<"    ";

    // }

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

using namespace std;

long long s,n,i,j,a,b,o[1000000]= {1,1},k[1000009];

int main() {

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

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

			o[j]=1;

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

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

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

		}

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

	}

	cin>>n;

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

		cin>>a>>b;

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

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4016250655751668x):
#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<iostream>

#include<algorithm>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<iomanip>

#include<vector>

#include<queue>

#include<set>

#include<map>

using namespace std;

int n;

int p[100005],f[100005];

int main()

{

	p[1]=1;

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

    {

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

        p[j]=1;

    }

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

    {

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

		{

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

		}

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

    }

	scanf("%d",&n);

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

	{

		int x,y;

		scanf("%d%d",&x,&y);

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



	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.5748963246660865x):
#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 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: 1.5748616560152726x):
#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;

#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;

  }

// Faster C++ solution for the same problem (measured speedup: 1.5917190419106217x):
#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<iostream>

#include<cstring>

using namespace std;

bool zs[100005];

int ans[100005],l,r;

main(){

	memset(zs,1,sizeof(zs));

	zs[0]=zs[1]=false;

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

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

			zs[j]=false;

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

		if (zs[i]&&zs[(i+1)/2]&&i!=2) ans[i]=ans[i-1]+1;

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

	int t;

	cin>>t;

	while(t--) {

		cin>>l>>r;

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

	}

	return 0;

}

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

using namespace std;

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

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;

        }

    }

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

#include<cstring>

using namespace std;

bool zs[100005];

int ans[100005],l,r;

main(){

	memset(zs,1,sizeof(zs));

	zs[0]=zs[1]=false;

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

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

			zs[j]=false;

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

		if (zs[i]&&zs[(i+1)/2]&&i!=2) ans[i]=ans[i-1]+1;

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

	int t;

	cin>>t;

	while(t--) {

		cin>>l>>r;

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

	}

	return 0;

}

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

using namespace std;

inline int read()

{

	int w=1,d=0; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1; ch=getchar();}

	while(ch>='0'&&ch<='9') d=d*10+ch-'0',ch=getchar();

	return w*d;

}

const int N = 1e5+7,M = 1e5+1;

bool p[N],v[N];

inline void primes()

{

	memset(v,0,sizeof(v));

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

	{

		if(v[i]) continue;

		p[i]=1;

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

	}

}

long long sum[N];

int main()

{

	primes();

	for(register int i=2;i<=M;i++)

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

	{

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

	}

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

	int q=read();

	while(q--)

	{

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

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

	}

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

using namespace std;

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

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;

        }

    }

    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;

}

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

using namespace std;

inline int read()

{

	int w=1,d=0; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1; ch=getchar();}

	while(ch>='0'&&ch<='9') d=d*10+ch-'0',ch=getchar();

	return w*d;

}

const int N = 1e5+7,M = 1e5+1;

bool p[N],v[N];

inline void primes()

{

	memset(v,0,sizeof(v));

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

	{

		if(v[i]) continue;

		p[i]=1;

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

	}

}

long long sum[N];

int main()

{

	primes();

	for(register int i=2;i<=M;i++)

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

	{

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

	}

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

	int q=read();

	while(q--)

	{

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

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

	}

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

#include<cstring>

using namespace std;

bool zs[100005];

int ans[100005],l,r;

main(){

	memset(zs,1,sizeof(zs));

	zs[0]=zs[1]=false;

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

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

			zs[j]=false;

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

		if (zs[i]&&zs[(i+1)/2]&&i!=2) ans[i]=ans[i-1]+1;

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

	int t;

	cin>>t;

	while(t--) {

		cin>>l>>r;

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

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.522411476483412x):
// #define debug

#ifdef debug

#include <time.h>

#include "/home/majiao/mb.h"

#endif





#include <iostream>

#include <algorithm>

#include <vector>

#include <string.h>

#define MAXN 100005

#include <map>

#include <unordered_set>

#define IS_PRIME(x) (!vis[x])

#define ll long long int



using namespace std;



int prime[MAXN], n, pn, vis[MAXN];

int sum[MAXN]; //统计符合要求的前缀和



void get_prime() {

	vis[0] = vis[1] = true;

	int MN = MAXN- 1;

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

		if(!vis[i]) {

			prime[pn++] = i;

		}

		if(i!=2 && IS_PRIME(i) && IS_PRIME((i+1)>>1))

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

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



		for(int k=0; k<pn && i*prime[k]<MN; k++) {

			vis[i*prime[k]] = true;

			if(i%prime[k] == 0) break;

		}

	}

}



int main() {

#ifdef debug

	freopen("test", "r", stdin);

	clock_t stime = clock();

#endif

	get_prime();

//	forarr(prime, 0, 13);

//	forarr(sum, 0, 7);

	int Q, lef, rig;

	scanf("%d ", &Q);

	while(Q--) {

		scanf("%d %d ", &lef, &rig);

		printf("%d\n", sum[rig]-sum[lef-1]);

	}









#ifdef debug

	clock_t etime = clock();

	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);

#endif 

	return 0;

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

using namespace std;

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

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;

        }

    }

    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;

}

// Faster C++ solution for the same problem (measured speedup: 1.2211543319116707x):
// #define debug

#ifdef debug

#include <time.h>

#include "/home/majiao/mb.h"

#endif





#include <iostream>

#include <algorithm>

#include <vector>

#include <string.h>

#define MAXN 100005

#include <map>

#include <unordered_set>

#define IS_PRIME(x) (!vis[x])

#define ll long long int



using namespace std;



int prime[MAXN], n, pn, vis[MAXN];

int sum[MAXN]; //统计符合要求的前缀和



void get_prime() {

	vis[0] = vis[1] = true;

	int MN = MAXN- 1;

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

		if(!vis[i]) {

			prime[pn++] = i;

		}

		if(i!=2 && IS_PRIME(i) && IS_PRIME((i+1)>>1))

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

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



		for(int k=0; k<pn && i*prime[k]<MN; k++) {

			vis[i*prime[k]] = true;

			if(i%prime[k] == 0) break;

		}

	}

}



int main() {

#ifdef debug

	freopen("test", "r", stdin);

	clock_t stime = clock();

#endif

	get_prime();

//	forarr(prime, 0, 13);

//	forarr(sum, 0, 7);

	int Q, lef, rig;

	scanf("%d ", &Q);

	while(Q--) {

		scanf("%d %d ", &lef, &rig);

		printf("%d\n", sum[rig]-sum[lef-1]);

	}









#ifdef debug

	clock_t etime = clock();

	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);

#endif 

	return 0;

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

#include<cstring>

using namespace std;

bool zs[100005];

int ans[100005],l,r;

main(){

	memset(zs,1,sizeof(zs));

	zs[0]=zs[1]=false;

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

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

			zs[j]=false;

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

		if (zs[i]&&zs[(i+1)/2]&&i!=2) ans[i]=ans[i-1]+1;

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

	int t;

	cin>>t;

	while(t--) {

		cin>>l>>r;

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

	}

	return 0;

}

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

using namespace std;

int a[100001],b[100002];

int q;

void init()

{

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

  {

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

    {

      if(a[j]==-1)

      {

        a[j]=0;

      }

    }

  }

}

void itit()

{

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

  {

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

    {

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

    }

    else

    b[i]=b[i-1];

  }

}

int main()

{

  int n,m;

  cin>>q;

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

  init();

  itit();

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

  {

    cin>>n>>m;

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

  }

  return 0;

}