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

}


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

using namespace std;



const int N = 1e5 + 10;

bool mark[N];

int q, ps[N];



int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	

	cin >> q;

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

		mark[i] = 1;

	mark[1] = 0;

	

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

		if(!mark[i])

			continue;

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

			mark[j] = 0;

	}

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

		ps[i] = ps[i - 1];

		if(i % 2 == 1)

			ps[i] += (mark[i] && mark[(i + 1) / 2]);

	}

	

	while(q){

		int l, r;

		cin >> l >> r;

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

		q--;

	}

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

}


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

using namespace std;



const int N = 1e5 + 10;

bool mark[N];

int q, ps[N];



int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	

	cin >> q;

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

		mark[i] = 1;

	mark[1] = 0;

	

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

		if(!mark[i])

			continue;

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

			mark[j] = 0;

	}

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

		ps[i] = ps[i - 1];

		if(i % 2 == 1)

			ps[i] += (mark[i] && mark[(i + 1) / 2]);

	}

	

	while(q){

		int l, r;

		cin >> l >> r;

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

		q--;

	}

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

}


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

using namespace std;



const int N = 1e5 + 10;

bool mark[N];

int q, ps[N];



int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	

	cin >> q;

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

		mark[i] = 1;

	mark[1] = 0;

	

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

		if(!mark[i])

			continue;

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

			mark[j] = 0;

	}

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

		ps[i] = ps[i - 1];

		if(i % 2 == 1)

			ps[i] += (mark[i] && mark[(i + 1) / 2]);

	}

	

	while(q){

		int l, r;

		cin >> l >> r;

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

		q--;

	}

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

}


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

using namespace std;



const int N = 1e5 + 10;

bool mark[N];

int q, ps[N];



int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	

	cin >> q;

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

		mark[i] = 1;

	mark[1] = 0;

	

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

		if(!mark[i])

			continue;

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

			mark[j] = 0;

	}

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

		ps[i] = ps[i - 1];

		if(i % 2 == 1)

			ps[i] += (mark[i] && mark[(i + 1) / 2]);

	}

	

	while(q){

		int l, r;

		cin >> l >> r;

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

		q--;

	}

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

}

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

using namespace std;



const int N = 1e5 + 10;

bool mark[N];

int q, ps[N];



int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	

	cin >> q;

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

		mark[i] = 1;

	mark[1] = 0;

	

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

		if(!mark[i])

			continue;

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

			mark[j] = 0;

	}

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

		ps[i] = ps[i - 1];

		if(i % 2 == 1)

			ps[i] += (mark[i] && mark[(i + 1) / 2]);

	}

	

	while(q){

		int l, r;

		cin >> l >> r;

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

		q--;

	}

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

}


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



using namespace std;



#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define REP(i,n) for(int i=0;i<(n);++i)

#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a))

#define mp make_pair

#define All(a) (a).begin(), (a).end()

template <typename T=int>

inline T IN(){T x; cin>>x; return(x);}

inline void CIN(){}

template <class Head,class... Tail>

inline void CIN(Head&& head,Tail&&... tail){

    cin>>head;

    CIN(move(tail)...);

}

#define CINT(...) int __VA_ARGS__;CIN(__VA_ARGS__)

#define LCIN(...) ll __VA_ARGS__;CIN(__VA_ARGS__)

#define SCIN(...) string __VA_ARGS__;CIN(__VA_ARGS__)



typedef long long ll;

typedef vector<int> V;

typedef vector<ll> VL;

typedef pair<int,int> P;

typedef pair<ll,ll> PL;

typedef priority_queue<int> PQ;

typedef priority_queue<int,V,greater<int>> PQG;



const int INF = 1e9;

const int MOD = 1e9+7;

const ll LINF = 1e18;



int Q;

const int rmax=1e5;

bool is_prime[rmax+1];

int prime[rmax+1];

int prisum[rmax+1];



int sieve(int n){

    int p=0;

    REP(i,n+1) is_prime[i]=true;

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

    REP(i,n+1){

        if(is_prime[i]==true){

            prime[p++]=i;

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

                is_prime[j]=false;

            }

        }

    }

    return p;

}



int main(){

    cin>>Q;

    sieve(rmax);

    REP(i,rmax+1){

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

            prisum[i]=1;

        }

    }

    FOR(i,1,rmax+1){

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

    }

    REP(i,Q){

        CINT(l,r);

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

    }

    return 0;

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

}


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



using namespace std;



#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define REP(i,n) for(int i=0;i<(n);++i)

#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a))

#define mp make_pair

#define All(a) (a).begin(), (a).end()

template <typename T=int>

inline T IN(){T x; cin>>x; return(x);}

inline void CIN(){}

template <class Head,class... Tail>

inline void CIN(Head&& head,Tail&&... tail){

    cin>>head;

    CIN(move(tail)...);

}

#define CINT(...) int __VA_ARGS__;CIN(__VA_ARGS__)

#define LCIN(...) ll __VA_ARGS__;CIN(__VA_ARGS__)

#define SCIN(...) string __VA_ARGS__;CIN(__VA_ARGS__)



typedef long long ll;

typedef vector<int> V;

typedef vector<ll> VL;

typedef pair<int,int> P;

typedef pair<ll,ll> PL;

typedef priority_queue<int> PQ;

typedef priority_queue<int,V,greater<int>> PQG;



const int INF = 1e9;

const int MOD = 1e9+7;

const ll LINF = 1e18;



int Q;

const int rmax=1e5;

bool is_prime[rmax+1];

int prime[rmax+1];

int prisum[rmax+1];



int sieve(int n){

    int p=0;

    REP(i,n+1) is_prime[i]=true;

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

    REP(i,n+1){

        if(is_prime[i]==true){

            prime[p++]=i;

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

                is_prime[j]=false;

            }

        }

    }

    return p;

}



int main(){

    cin>>Q;

    sieve(rmax);

    REP(i,rmax+1){

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

            prisum[i]=1;

        }

    }

    FOR(i,1,rmax+1){

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

    }

    REP(i,Q){

        CINT(l,r);

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

    }

    return 0;

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

}


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

#include <unordered_set>

#include <algorithm>

#include <iostream>

#include <numeric>

#include <cstring>

#include <cassert>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <cmath>

#include <set>

#include <map>

#include <functional>

#include <iomanip>

#include <bitset>



using namespace std;

#define     loop(n,i,a)     for(int i=a;i<n;i++)

#define     all(arr,n)      arr,arr+n

#define     allv(v)         (v).begin(),(v).end()

#define     rallv(v)        (v).rbegin(),(v).rend()

#define     m_p             make_pair

#define     ll              long long

#define     vi              vector<int>

#define     vll             vector<ll>

#define     sz(x)           (int)x.size()

#define     pb              push_back

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

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

const int N=(int)1e5+6;

vector<bool>primes(N);

void sieve(){

	fill(allv(primes),1);

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

	loop(N,i,2){

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

			primes[j]=0;

	}

}

int main() {

	sieve();

	int cum[N]={},q;

	loop(N,i,2){

		cum[i]+=(cum[i-1]+(primes[i]&&primes[(i+1)/2]));

	}

	cin>>q;

	while(q--){

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

		cout<<cum[r]-cum[l-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.7341890695737765x):
#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;

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

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

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: 2.0532904890574284x):
#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;

}