stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>



const int PRIME_MAX = 1e5+100;



int main(){

    using namespace std;

    int Q; cin >> Q;

    vector<int> l(Q), r(Q);

    vector<int> n_like(PRIME_MAX, 0);

    for (int i = 0; i < Q; i++) cin >> l[i] >> r[i];



    vector<bool> is_prime(PRIME_MAX, true);

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

    for (int i = 4; i < PRIME_MAX; i+=2) is_prime[i] = false;

    for (int i = 3; i < PRIME_MAX; i+=2)

    {

        if(!is_prime[i]) continue;

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

    }

    

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

    {

        if(i%2==1 && is_prime[i] && is_prime[(i+1)/2]) n_like[i] = n_like[i-1] + 1;

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

    }

    

    for (int i = 0; i < Q; i++)

    {

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

    }

}


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



/*

template<size_t max_N>

struct Prime{

    bool is_prime[max_N];

    constexpr Prime() : is_prime() {

        for(int i = 0; i < max_N; i++) is_prime[i] = true;

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

        for (int i = 0; i < max_N; i++)

        {

            if(!is_prime[i]) continue;

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

        }

        

    }

};

*/



template<size_t max_N, size_t prime_size>

struct Prime{

    bool sieve[max_N];

    int_fast64_t prime[prime_size];

    size_t counter = 0;

    constexpr Prime() : sieve(), prime() {

        for(int_fast64_t i = 0; i < max_N; ++i)

            sieve[i] = true;

        sieve[0] = sieve[1] = false;

        for(int_fast64_t i = 2; i < max_N; ++i){

            if(sieve[i]){

                prime[counter] = i;

                ++counter;

                if(counter > prime_size)break;

            }

            for(int_fast64_t j = i * i; j < max_N; j += i)

                sieve[j] = false;

        }

    }

};

int main(){

    using namespace std;

    const int PRIME_MAX = 1e5+100;

    int Q; cin >> Q;

    vector<int> l(Q), r(Q);

    vector<int> n_like(PRIME_MAX, 0);

    for (int i = 0; i < Q; i++) cin >> l[i] >> r[i];

    constexpr auto p = Prime<PRIME_MAX, 10000>();

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

    {

        if(i%2==1 && p.sieve[i] && p.sieve[(i+1)/2]) n_like[i] = n_like[i-1] + 1;

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

    }

    

    for (int i = 0; i < Q; i++)

    {

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

    }

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

#include <vector>

#define MAX_N 100001



using namespace std;



vector<bool> IsPrime(MAX_N, true);



// エラトステネスの篩

void get_primes() {

    IsPrime[0] = false;

    IsPrime[1] = false;



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

        if (IsPrime[i]) {

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

                IsPrime[j]= false;

            }

        }

    }

}



int main() {

    int Q, l, r;

    vector<int> cnt(MAX_N, 0);



    get_primes();



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

        if (IsPrime[i] && IsPrime[(i+1)/2]) { cnt[i]++; }

    }

    // 2017 に似てる数の累積和をとっている

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

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

    }



    cin >> Q;



    while (Q--) {

        cin >> l >> r;

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

    }



    return 0;

}

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

#include <cstring>

#define MAX_N 100001



bool IsPrime[MAX_N];



void get_primes() {

    IsPrime[0] = false;

    IsPrime[1] = false;



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

        if (IsPrime[i]) {

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

                IsPrime[j]= false;

            }

        }

    }

}



int main() {

    int Q, l, r;

    int cnt[MAX_N] = {0};



    memset(IsPrime, 1, sizeof(IsPrime));

    get_primes();



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

        if (IsPrime[i] && IsPrime[(i+1)/2]) { cnt[i]++; }

    }

    // 2017 に似てる数の累積和をとっている

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

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

    }



    scanf("%d", &Q);



    while (Q--) {

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

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

    }



    return 0;

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

#include <vector>

#define MAX_N 100001



using namespace std;



vector<bool> IsPrime(MAX_N, true);



// エラトステネスの篩

void get_primes() {

    IsPrime[0] = false;

    IsPrime[1] = false;



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

        if (IsPrime[i]) {

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

                IsPrime[j]= false;

            }

        }

    }

}



int main() {

    int Q, l, r;

    vector<int> cnt(MAX_N, 0);



    get_primes();



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

        if (IsPrime[i] && IsPrime[(i+1)/2]) { cnt[i]++; }

    }

    // 2017 に似てる数の累積和をとっている

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

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

    }



    cin >> Q;



    while (Q--) {

        cin >> l >> r;

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

    }



    return 0;

}

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

#include <cstring>

#define MAX_N 100001



bool IsPrime[MAX_N + 1];



// エラトステネスの篩

void get_primes() {

    IsPrime[0] = false;

    IsPrime[1] = false;



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

        if (IsPrime[i]) {

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

                IsPrime[j]= false;

            }

        }

    }

}



int main() {

    int Q, l, r;

    int cnt[MAX_N + 1] = {0};



    memset(IsPrime, 1, sizeof(IsPrime));

    get_primes();



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

        if (IsPrime[i] && IsPrime[(i+1)/2]) { cnt[i]++; }

    }



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

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

    }



    scanf("%d", &Q);



    while (Q--) {

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

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

    }



    return 0;

}
// 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.6388827787608538x):
#include <bits/stdc++.h>





using namespace std;



typedef long long ll;



const int MAXN = 100 * 1000 + 123;









bool inp[MAXN];

int ps[MAXN];



void gh() {

	inp[0] = inp[1] = true;

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

		if (!inp[i])

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

				inp[j] = true;

}





int main() {

	gh();

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

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

		if (!inp[i - 1] && !inp[i >> 1])

			ps[i]++;

	}

	int q, l, r;

	cin >> q;

	while (q--) {

		cin >> l >> r;

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

	}

	return 0;

}
// Slower C++ solution:
/**

*　　　　　　　　┏┓　　 　┏┓

* 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓

* 　　　　　　　┃　　　　　　　┃ 　

* 　　　　　　　┃　　　━　　 　┃

* 　　　　　　　┃　＞　　　＜　┃

* 　　　　　　　┃　　　　　　　┃

* 　　　　　　　┃...　⌒　... 　┃

* 　　　　　　　┃　　　　　　　┃

* 　　　　　　　┗━┓　　　┏━┛

* 　　　　　　　　　┃　　　┃　　　　　　　　　　

* 　　　　　　　　　┃　　　┃

* 　　　　　　　　　┃　　　┃　　　　　　　　　　　

* 　　　　　　　　　┃　　　┃  　　　　　　

* 　　　　　　　　　┃　　　┃

* 　　　　　　　　　┃　　　┃　　　　　　　　　　　

* 　　　　　　　　　┃　　　┗━━━┓

* 　　　　　　　　　┃　　　　　　　┣┓

* 　　　　　　　　　┃　　　　　　　┏┛

* 　　　　　　　　　┗┓┓┏━┳┓┏┛

* 　　　　　　　　　　┃┫┫　┃┫┫

* 　　　　　　　　　　┗┻┛　┗┻┛

*/

#include<iostream>  

#include<cstdio>  

#include<fstream>  

#include<iomanip>

#include<algorithm>  

#include<cmath>  

#include<deque>  

#include<vector>

#include<bitset>

#include<queue>  

#include<string>  

#include<cstring>  

#include<map>  

#include<stack>  

#include<set>

#include<cassert>

#include<functional>



#define pii pair<int, int>

#define mod 1000000007

#define mp make_pair

#define pi acos(-1)

#define eps 0.000000001

#define mst(a,i) memset(a,i,sizeof(a))

#define all(n) n.begin(),n.end()

#define lson(x) ((x<<1))  

#define rson(x) ((x<<1)|1) 

#define inf 0x3f3f3f3f

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;



vector<int>prime;

int isprime[maxn];



void getprimelist(int t)

{

	mst(isprime, 1);

	isprime[1] = 0;

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

	{

		if (isprime[i])prime.push_back(i);

		for (int j = 0; j < prime.size() && prime[j] * i <= t; ++j)

		{

			isprime[prime[j] * i] = 0;

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

		}

	}

}

int ok[maxn];

int main()

{

	ios::sync_with_stdio(false);

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

#ifdef DEBUG

	freopen("old_data.json", "r", stdin);

	freopen("1.out", "w", stdout);

#endif // DEBUG clang++ checker.cpp --target=i686-pc-mingw32 -o checker.exe

	int n;

	getprimelist(100000);

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

		if (isprime[i] && isprime[(i + 1) / 2])ok[i] = 1;

	}

	for (int i = 1; i <= 100000; ++i)ok[i] += ok[i - 1];

	cin >> n;

	int l, r;

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

		cin >> l >> r;

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

	}

	return 0;

}

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





using namespace std;



typedef long long ll;



const int MAXN = 100 * 1000 + 123;









bool inp[MAXN];

int ps[MAXN];



void gh() {

	inp[0] = inp[1] = true;

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

		if (!inp[i])

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

				inp[j] = true;

}





int main() {

	gh();

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

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

		if (!inp[i - 1] && !inp[i >> 1])

			ps[i]++;

	}

	int q, l, r;

	cin >> q;

	while (q--) {

		cin >> l >> r;

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

	}

	return 0;

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

using namespace std;



#define int long long



const int N = 1e5 + 10;

int q, mark[N], psum[N];



int32_t main() {

	ios::sync_with_stdio(0);

	cin.tie(0);

	

	mark[1] = 1;

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

		if (!mark[i])

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

				mark[j] = 1;

				

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

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

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

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

	

	cin >> q;

	while (q--) {

		int l, r;

		cin >> l >> r;

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

	}

}

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





using namespace std;



typedef long long ll;



const int MAXN = 100 * 1000 + 123;









bool inp[MAXN];

int ps[MAXN];



void gh() {

	inp[0] = inp[1] = true;

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

		if (!inp[i])

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

				inp[j] = true;

}





int main() {

	gh();

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

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

		if (!inp[i - 1] && !inp[i >> 1])

			ps[i]++;

	}

	int q, l, r;

	cin >> q;

	while (q--) {

		cin >> l >> r;

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

	}

	return 0;

}
// 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.6085710264455284x):
#include <bits/stdc++.h>

using namespace std;

const int n=1e5+10;

bitset<n> isprime;

vector<int>answer;

//here are different comments

//to test the expirement

//oh wow hi

void sieve()

{

    isprime[0]=isprime[1]=0;

    for(int p=2; p<=n; ++p)

        if(isprime[p])

            for(int m=2*p; m<n; m+=p)

                isprime[m]=0;



}





int the2017ers[n];

void is2017()

{

    int sum=0;

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

    {



        sum+=(isprime[p]&&isprime[(p+1)/2]);

        the2017ers[p]=sum;



    }



}



int main()

{



    isprime.set();

    sieve();

    is2017();

    int tc,l,r;

    cin>>tc;

    while(tc--)

    {

        cin>>l>>r;

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

    }





    return 0;

}
// Slower C++ solution:
/**

*　　　　　　　　┏┓　　 　┏┓

* 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓

* 　　　　　　　┃　　　　　　　┃ 　

* 　　　　　　　┃　　　━　　 　┃

* 　　　　　　　┃　＞　　　＜　┃

* 　　　　　　　┃　　　　　　　┃

* 　　　　　　　┃...　⌒　... 　┃

* 　　　　　　　┃　　　　　　　┃

* 　　　　　　　┗━┓　　　┏━┛

* 　　　　　　　　　┃　　　┃　　　　　　　　　　

* 　　　　　　　　　┃　　　┃

* 　　　　　　　　　┃　　　┃　　　　　　　　　　　

* 　　　　　　　　　┃　　　┃  　　　　　　

* 　　　　　　　　　┃　　　┃

* 　　　　　　　　　┃　　　┃　　　　　　　　　　　

* 　　　　　　　　　┃　　　┗━━━┓

* 　　　　　　　　　┃　　　　　　　┣┓

* 　　　　　　　　　┃　　　　　　　┏┛

* 　　　　　　　　　┗┓┓┏━┳┓┏┛

* 　　　　　　　　　　┃┫┫　┃┫┫

* 　　　　　　　　　　┗┻┛　┗┻┛

*/

#include<iostream>  

#include<cstdio>  

#include<fstream>  

#include<iomanip>

#include<algorithm>  

#include<cmath>  

#include<deque>  

#include<vector>

#include<bitset>

#include<queue>  

#include<string>  

#include<cstring>  

#include<map>  

#include<stack>  

#include<set>

#include<cassert>

#include<functional>



#define pii pair<int, int>

#define mod 1000000007

#define mp make_pair

#define pi acos(-1)

#define eps 0.000000001

#define mst(a,i) memset(a,i,sizeof(a))

#define all(n) n.begin(),n.end()

#define lson(x) ((x<<1))  

#define rson(x) ((x<<1)|1) 

#define inf 0x3f3f3f3f

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;



vector<int>prime;

int isprime[maxn];



void getprimelist(int t)

{

	mst(isprime, 1);

	isprime[1] = 0;

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

	{

		if (isprime[i])prime.push_back(i);

		for (int j = 0; j < prime.size() && prime[j] * i <= t; ++j)

		{

			isprime[prime[j] * i] = 0;

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

		}

	}

}

int ok[maxn];

int main()

{

	ios::sync_with_stdio(false);

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

#ifdef DEBUG

	freopen("old_data.json", "r", stdin);

	freopen("1.out", "w", stdout);

#endif // DEBUG clang++ checker.cpp --target=i686-pc-mingw32 -o checker.exe

	int n;

	getprimelist(100000);

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

		if (isprime[i] && isprime[(i + 1) / 2])ok[i] = 1;

	}

	for (int i = 1; i <= 100000; ++i)ok[i] += ok[i - 1];

	cin >> n;

	int l, r;

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

		cin >> l >> r;

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

	}

	return 0;

}

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

using namespace std;

const int n=1e5+10;

bitset<n> isprime;

vector<int>answer;

//here are different comments

//to test the expirement

//oh wow hi

void sieve()

{

    isprime[0]=isprime[1]=0;

    for(int p=2; p<=n; ++p)

        if(isprime[p])

            for(int m=2*p; m<n; m+=p)

                isprime[m]=0;



}





int the2017ers[n];

void is2017()

{

    int sum=0;

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

    {



        sum+=(isprime[p]&&isprime[(p+1)/2]);

        the2017ers[p]=sum;



    }



}



int main()

{



    isprime.set();

    sieve();

    is2017();

    int tc,l,r;

    cin>>tc;

    while(tc--)

    {

        cin>>l>>r;

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

    }





    return 0;

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

using namespace std;



#define int long long



const int N = 1e5 + 10;

int q, mark[N], psum[N];



int32_t main() {

	ios::sync_with_stdio(0);

	cin.tie(0);

	

	mark[1] = 1;

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

		if (!mark[i])

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

				mark[j] = 1;

				

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

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

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

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

	

	cin >> q;

	while (q--) {

		int l, r;

		cin >> l >> r;

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

	}

}

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

using namespace std;

const int n=1e5+10;

bitset<n> isprime;

vector<int>answer;

//here are different comments

//to test the expirement

//oh wow hi

void sieve()

{

    isprime[0]=isprime[1]=0;

    for(int p=2; p<=n; ++p)

        if(isprime[p])

            for(int m=2*p; m<n; m+=p)

                isprime[m]=0;



}





int the2017ers[n];

void is2017()

{

    int sum=0;

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

    {



        sum+=(isprime[p]&&isprime[(p+1)/2]);

        the2017ers[p]=sum;



    }



}



int main()

{



    isprime.set();

    sieve();

    is2017();

    int tc,l,r;

    cin>>tc;

    while(tc--)

    {

        cin>>l>>r;

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

    }





    return 0;

}
// 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.2523259658220212x):
#include<bits/stdc++.h>

using namespace std;



#define INF 1e5 



int prise[100006],f[100006];

bool isprise[100006];



void os(int r)

{

	int tot=0;

	memset(isprise,1,sizeof(isprise));

	isprise[1]=isprise[0]=0;

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

	{

		if(isprise[i])

			prise[tot++]=i;

		for(int j=0;i*prise[j]<=r;j++)

		{

			isprise[i*prise[j]]=0;

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

				break;

		}

	}

}



void Prefix_and()

{

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

	{

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

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

			f[i]++;

	}

}



int main()

{

	int n,x,y;

	os(100005);

	Prefix_and();

	cin>>n;

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

	{

		cin>>x>>y;

		cout<<f[y]-f[x-1]<<endl;

	}

	return 0;

}
// Slower C++ solution:
/**

*　　　　　　　　┏┓　　 　┏┓

* 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓

* 　　　　　　　┃　　　　　　　┃ 　

* 　　　　　　　┃　　　━　　 　┃

* 　　　　　　　┃　＞　　　＜　┃

* 　　　　　　　┃　　　　　　　┃

* 　　　　　　　┃...　⌒　... 　┃

* 　　　　　　　┃　　　　　　　┃

* 　　　　　　　┗━┓　　　┏━┛

* 　　　　　　　　　┃　　　┃　　　　　　　　　　

* 　　　　　　　　　┃　　　┃

* 　　　　　　　　　┃　　　┃　　　　　　　　　　　

* 　　　　　　　　　┃　　　┃  　　　　　　

* 　　　　　　　　　┃　　　┃

* 　　　　　　　　　┃　　　┃　　　　　　　　　　　

* 　　　　　　　　　┃　　　┗━━━┓

* 　　　　　　　　　┃　　　　　　　┣┓

* 　　　　　　　　　┃　　　　　　　┏┛

* 　　　　　　　　　┗┓┓┏━┳┓┏┛

* 　　　　　　　　　　┃┫┫　┃┫┫

* 　　　　　　　　　　┗┻┛　┗┻┛

*/

#include<iostream>  

#include<cstdio>  

#include<fstream>  

#include<iomanip>

#include<algorithm>  

#include<cmath>  

#include<deque>  

#include<vector>

#include<bitset>

#include<queue>  

#include<string>  

#include<cstring>  

#include<map>  

#include<stack>  

#include<set>

#include<cassert>

#include<functional>



#define pii pair<int, int>

#define mod 1000000007

#define mp make_pair

#define pi acos(-1)

#define eps 0.000000001

#define mst(a,i) memset(a,i,sizeof(a))

#define all(n) n.begin(),n.end()

#define lson(x) ((x<<1))  

#define rson(x) ((x<<1)|1) 

#define inf 0x3f3f3f3f

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;



vector<int>prime;

int isprime[maxn];



void getprimelist(int t)

{

	mst(isprime, 1);

	isprime[1] = 0;

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

	{

		if (isprime[i])prime.push_back(i);

		for (int j = 0; j < prime.size() && prime[j] * i <= t; ++j)

		{

			isprime[prime[j] * i] = 0;

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

		}

	}

}

int ok[maxn];

int main()

{

	ios::sync_with_stdio(false);

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

#ifdef DEBUG

	freopen("old_data.json", "r", stdin);

	freopen("1.out", "w", stdout);

#endif // DEBUG clang++ checker.cpp --target=i686-pc-mingw32 -o checker.exe

	int n;

	getprimelist(100000);

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

		if (isprime[i] && isprime[(i + 1) / 2])ok[i] = 1;

	}

	for (int i = 1; i <= 100000; ++i)ok[i] += ok[i - 1];

	cin >> n;

	int l, r;

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

		cin >> l >> r;

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

	}

	return 0;

}

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

using namespace std;



#define INF 1e5 



int prise[100006],f[100006];

bool isprise[100006];



void os(int r)

{

	int tot=0;

	memset(isprise,1,sizeof(isprise));

	isprise[1]=isprise[0]=0;

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

	{

		if(isprise[i])

			prise[tot++]=i;

		for(int j=0;i*prise[j]<=r;j++)

		{

			isprise[i*prise[j]]=0;

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

				break;

		}

	}

}



void Prefix_and()

{

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

	{

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

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

			f[i]++;

	}

}



int main()

{

	int n,x,y;

	os(100005);

	Prefix_and();

	cin>>n;

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

	{

		cin>>x>>y;

		cout<<f[y]-f[x-1]<<endl;

	}

	return 0;

}