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

}

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

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

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

    }

}

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

using namespace std;

#define ll long long

const int MAX = 1e5 + 10;

int prime[MAX], tag[MAX], f[MAX];

void is_Prime(){

	int cnt = 0;

	prime[++cnt] = 2;

	tag[1] = 1;

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

		if(!tag[i])

			prime[++cnt] = i;

		for(int j = 1; j <= cnt && i * prime[j] < MAX; j++){

			tag[i * prime[j]] = 1;

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

				break;

		}

	}

}

int main(){

	int t, l, r, num = 0;

	is_Prime();

	

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

    {

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

            {

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

            }

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

    }

    

	cin >> t;

	while(t--){

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

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

	}

	return  0;

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

using namespace std;

int p[100009],f[100009];

main() {

	p[1]=1;



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

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

			p[j]=1;

	}

	p[2]=0;

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

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

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

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

	}

	int q;

	cin>>q;

	while(q--) {

		int l,r;

		cin>>l>>r;

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

	}

}

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

using namespace std;

#define ll long long

const int MAX = 1e5 + 10;

int prime[MAX], tag[MAX], f[MAX];

void is_Prime(){

	int cnt = 0;

	prime[++cnt] = 2;

	tag[1] = 1;

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

		if(!tag[i])

			prime[++cnt] = i;

		for(int j = 1; j <= cnt && i * prime[j] < MAX; j++){

			tag[i * prime[j]] = 1;

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

				break;

		}

	}

}

int main(){

	int t, l, r, num = 0;

	is_Prime();

	

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

    {

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

            {

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

            }

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

    }

    

	cin >> t;

	while(t--){

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

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

	}

	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.2735478897077925x):
#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";

	}

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

    }

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

	}

}

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

    }

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

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

	}

}

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

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

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

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

using namespace std;

const int N = 100000;

int prime[N+10];

int pre[N+10];

void isPrime() {

	prime[1] = 1;

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

		if(!prime[i]) {

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

				prime[j] = 1;

		}

	}

}

bool isLike(int x) {

	if (prime[x] == 0 && prime[(x+1) / 2] == 0) {

		return true;

	}

	return false;

}

void pre_sum(){

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

		if (isLike(j)) {

			pre[j] = pre[j - 1] + 1;

		} else {

			pre[j] = pre[j - 1];

		}

	}

}

int main() {

	isPrime();

	pre_sum();

	int n, a, b;

	cin >> n;

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

		cin >> a >> b;

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

	}

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

using namespace std;

const int N = 100000;

int prime[N+10];

int pre[N+10];

void isPrime() {

	prime[1] = 1;

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

		if(!prime[i]) {

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

				prime[j] = 1;

		}

	}

}

bool isLike(int x) {

	if (prime[x] == 0 && prime[(x+1) / 2] == 0) {

		return true;

	}

	return false;

}

void pre_sum(){

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

		if (isLike(j)) {

			pre[j] = pre[j - 1] + 1;

		} else {

			pre[j] = pre[j - 1];

		}

	}

}

int main() {

	isPrime();

	pre_sum();

	int n, a, b;

	cin >> n;

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

		cin >> a >> b;

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

	}

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

using namespace std;

const int N = 100000;

int prime[N+10];

int pre[N+10];

void isPrime() {

	prime[1] = 1;

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

		if(!prime[i]) {

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

				prime[j] = 1;

		}

	}

}

bool isLike(int x) {

	if (prime[x] == 0 && prime[(x+1) / 2] == 0) {

		return true;

	}

	return false;

}

void pre_sum(){

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

		if (isLike(j)) {

			pre[j] = pre[j - 1] + 1;

		} else {

			pre[j] = pre[j - 1];

		}

	}

}

int main() {

	isPrime();

	pre_sum();

	int n, a, b;

	cin >> n;

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

		cin >> a >> b;

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

	}

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

}