stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<cstdio>

#include<iostream>

using namespace std;

#define MAX 100001

int n;

int prime[MAX];

int cnt[MAX]={};

void eratos() {

	int j;

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

	//全部primeと設定する

	prime[i] = 1;

	}

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



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

	j = i+i;

	while(j<MAX) {

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

	j += i;

	}

	}

	

}



void like() {

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

	{

	if (i%2==1) {	

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

	++cnt[i];

	}

	}

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

	}

}







int main() {

	int q;

	int l,r;

	cin >> q;

	eratos();

	like();

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

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

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

	}



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

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

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

	}

*/

	return 0;

}


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

#include<iostream>

using namespace std;

#define MAX 100001

int n;

int prime[MAX];

int cnt[MAX]={};

void eratos() {

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

	//全部primeと設定する

	prime[i] = 1;

	}

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



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

	if (prime[i]) {

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

	prime[j] = 0;

	}

	}	

	}

}



void like() {

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

	{

	if (i%2==1) {	

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

	++cnt[i];

	}

	}

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

	}

}







int main() {

	int q;

	int l,r;

	cin >> q;

	eratos();

	like();

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

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

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

	}



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

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

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

	}

*/

	return 0;

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

#include<algorithm>

#include<string>

#include<map>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

typedef long long int llint;

typedef pair<ll, ll> pa;

#define MM 1000000000

#define MOD MM+7

#define MAX 101000

#define MAP 110

#define initial_value -1

#define Pair pair<int,int>

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

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

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

const ll DEP = 1e18;

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

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

int Q;

int main(){

    //エラトステネスの篩

    int MAXX = 101010;

    vector<int> is_prime(MAXX,1);

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

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

        if(!is_prime[i]) continue;

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

    }

    //2017-like

    vector<int> a(MAXX,0);

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

        if(i % 2 == 0) continue;

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

    }

    //累積和

    vector<int> s(MAXX,0);

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

    //クエリ

    cin >> Q;

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

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

        r++;

        cout << s[r] - s[l] << endl;

    }

}






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

#include<algorithm>

#include<string>

#include<map>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

typedef long long int llint;

typedef pair<ll, ll> pa;

#define MM 1000000000

#define MOD MM+7

#define MAX 101000

#define MAP 110

#define initial_value -1

#define MAX_T 1001

#define Pair pair<int,int>

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

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

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

const ll DEP = 1e18;

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

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

int main(){

    vector<bool> pr(100001,true);

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

        if(pr[i]){

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

                pr[j] = false;

            }

        }

    }

    vector<int> ans(100001,0);

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

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

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

    }

    int q; cin >> q;

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

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

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

    }

    return 0;

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



using namespace std;



#define td typedef

td long long ll;



ll in()

{

    ll a;

    scanf("%lld",&a);

    return a;

}



bool prime[100005];

int chumu[100005];



int main()

{

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

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

    {

        if(!prime[i])

        {

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

                prime[j]=1;

        }

    }

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

    {

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

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

        else

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

    }

    int t=in();

    while(t--)

    {

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

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

    }

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

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

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

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

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

using namespace std;



const int N = 1e5 + 100;



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

bool mark[N];



int main() {

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

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

		if(mark[i] == false) {

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

				mark[j] = true;

		}

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

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

	cin >> q;

	while(q--) {

		cin >> l >> r;

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

	}

	return 0;

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

using namespace std;



const int N = 1e5 + 100;



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

bool mark[N];



int main() {

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

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

		if(mark[i] == false) {

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

				mark[j] = true;

		}

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

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

	cin >> q;

	while(q--) {

		cin >> l >> r;

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

	}

	return 0;

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

using namespace std;



const int N = 1e5 + 100;



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

bool mark[N];



int main() {

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

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

		if(mark[i] == false) {

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

				mark[j] = true;

		}

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

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

	cin >> q;

	while(q--) {

		cin >> l >> r;

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

	}

	return 0;

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

using namespace std;



const int N = 1e5 + 100;



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

bool mark[N];



int main() {

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

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

		if(mark[i] == false) {

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

				mark[j] = true;

		}

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

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

	cin >> q;

	while(q--) {

		cin >> l >> r;

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

	}

	return 0;

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

using namespace std;



const int N = 1e5 + 100;



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

bool mark[N];



int main() {

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

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

		if(mark[i] == false) {

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

				mark[j] = true;

		}

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

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

	cin >> q;

	while(q--) {

		cin >> l >> r;

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

	}

	return 0;

}