stablegradients/pie-gem5-pairs huggingface dataset:
// 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.5271767631758337x):
#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<bits/stdc++.h>

using namespace std;



const int MAX_R = 1e5 + 3;

bool p[MAX_R+5];

int r[MAX_R+5];



void init() {

    for(int i = 0; i <= MAX_R + 1; ++i) p[i] = true;

    p[0] = p[1] = false;

    int i = 2;

    while(i <= MAX_R) {

        for(int j = 2; j*i <= MAX_R; ++j) p[j*i] = false;

        while(p[++i] == false);

    }

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

        r[i] = r[i-1];

        if(i > 0 && p[i] && p[(i+1)/2]) ++r[i];

    }

}



int main()

{

    int Q;

    cin >> Q;

    init();

    int c[Q+2];

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

        int L, R;

        cin >> L >> R;

        c[i] = r[R] - r[L-1];

    }

    for(int i = 0; i < Q; ++i) cout << c[i] << endl;

    return 0;

}

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

    }



    return 0;

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



using namespace std;



using ll = long long;

using ld = long double;



using vi = vector<int>;

using vvi = vector<vi>;

using vvvi = vector<vvi>;

using vl = vector<ll>;

using vvl = vector<vl>;

using vvvl = vector<vvl>;

using vd = vector<double>;

using vvd = vector<vd>;

using vb = vector<bool>;

using vvb = vector<vb>;

using vs = vector<string>;



const int INF = (1 << 30) - 1;

const ll INF64 = ((ll)1 << 62) - 1;

const double PI = 3.1415926535897932384626433832795;



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

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



int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

int lcm(int x, int y) { return x / gcd(x, y) * y; }

ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }



const int R_MAX = 100000;



int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);



	vector<bool> notPrimeNum(R_MAX + 1);

	notPrimeNum[0] = notPrimeNum[1] = true;

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

		if (notPrimeNum[i]) {

			continue;

		}

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

			notPrimeNum[j] = true;

		}

	}



	vector<int> cnt(R_MAX + 1);

	for (int i = 3; i <= R_MAX; i++) {

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

			cnt[i]++;

		}

	}

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

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

	}



	int q;

	cin >> q;

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

		int l, r;

		cin >> l >> r;

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

	}

	return 0;

}


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



using namespace std;



using ll = long long;

using ld = long double;



const int INF = (1 << 30) - 1;

const ll INF64 = ((ll)1 << 62) - 1;

const double PI = 3.1415926535897932384626433832795;



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

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



vector<bool> getPrime(int n) {

	vector<bool> prime(n + 1, true);



	if (n >= 0) prime[0] = false;

	if (n >= 1) prime[1] = false;



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

		if (prime[i]) {

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

				prime[j] = false;

			}

		}

	}



	return prime;

}



int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);



	const int R_MAX = 100000;

	vector<bool> prime = getPrime(R_MAX + 1);



	vector<int> cnt(R_MAX + 1);

	for (int i = 3; i <= R_MAX; i++) {

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

			cnt[i]++;

		}

	}

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

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

	}



	int q;

	cin >> q;



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

		int l, r;

		cin >> l >> r;



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

	}

	return 0;

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



using namespace std;



using ll = long long;

using ld = long double;



const double PI = 3.1415926535897932384626433832795;

const ll MOD = 1000000007;



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

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



int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }

int lcm(int x, int y) { return x / gcd(x, y) * y; }

ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }



vector<int> f(int n) {

	ll p = 0;



	vector<int> isPrime(n + 1, true);

	isPrime[0] = isPrime[1] = false;



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

		if (!isPrime[i]) {

			continue;

		}



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

			isPrime[j] = false;

		}

	}



	vector<int> a(n);

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

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

	}



	vector<int> memo(n + 1);

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

		memo[i] += memo[i - 1] + a[i - 1];

	}



	return memo;

}



int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);





	const int N_MAX = (int)1e5 + 30;

	vector<int> memo = f(N_MAX);



	int q;

	cin >> q;



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

		int l, r;

		cin >> l >> r;



		cout << memo[r + 1] - memo[l] << endl;

	}

	return 0;

}


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



using namespace std;



using ll = long long;

using ld = long double;



const double PI = 3.1415926535897932384626433832795;

const ll MOD = 1000000007;



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

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



int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }

int lcm(int x, int y) { return x / gcd(x, y) * y; }

ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }



vector<int> f(int n) {

	ll p = 0;



	vector<int> isPrime(n + 1, true);

	isPrime[0] = isPrime[1] = false;



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

		if (!isPrime[i]) {

			continue;

		}



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

			isPrime[j] = false;

		}

	}



	vector<int> a(n);

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

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

	}



	vector<int> memo(n + 1);

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

		memo[i] += memo[i - 1] + a[i - 1];

	}



	return memo;

}



int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);





	const int N_MAX = (int)1e5 + 30;

	vector<int> memo = f(N_MAX);



	int q;

	cin >> q;



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

		int l, r;

		cin >> l >> r;



		cout << memo[r + 1] - memo[l] << endl;

	}

	return 0;

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



using namespace std;



int main()

{

	bool prime[100001];

	int n, m;

	int c[100010] = {0};	

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

	int ans[100001] = {0};



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

		prime[i] = true;

	}



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

		if (prime[i]) {

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

				prime[j] = false;

			}

		}

	}



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

		if (prime[i] && prime[(i + 1) / 2]) c[i] = 1;

	}



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

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

	}



	int q;

	

	cin >> q;



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

		int r, l;

		cin >> l >> r;



		ans[i] = c[r] - c[l - 1];

	}

	

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

		cout << ans[i] << endl;

	}

}


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

#include <string>

#include <vector>

#include <map>

#include <algorithm>



using namespace std;



bool num[100010];



void eratosthenes(int n) {

    for (int i = 0; i <= n; i++) num[i] = true;



    num[0] = num[1] = false;



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

        if (num[i]) {

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

                num[j] = false;

            }

        }

    }

}



int main()

{

    int q;

    int l, r;

    int ans[100010] = {};

    int rui[100010] = {};

    vector<int> yeah;



    cin >> q;

    

    eratosthenes(100000);



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

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

            ans[i] = 1;

        }

    }



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

        rui[i+1] = rui[i] + ans[i];

    }



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

        cin >> l >> r;

        yeah.push_back(rui[r+1]-rui[l]);

    }



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

        cout << yeah[i] << endl;

    }



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

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  fflush(stdout);

  return 0;

}


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

#include <cmath>

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  fflush(stdout);

  return 0;

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

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  fflush(stdout);

  return 0;

}


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

#include <cmath>

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

  int const limit = sqrt(MAX);

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  fflush(stdout);

  return 0;

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

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  fflush(stdout);

  return 0;

}


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

#include <cmath>

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  fflush(stdout);

  return 0;

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

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  fflush(stdout);

  return 0;

}


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

#include <cmath>

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  return 0;

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

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  fflush(stdout);

  return 0;

}


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

#include <cmath>

 

#define MAX 100000



bool prime[MAX + 1];

int count[MAX + 1];

int N, L, R;



int main() {

  // 素数配列をエラトステネスの篩を使って生成

  // 素数であれば false, 素数でなければ true

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

    if (!prime[i])

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

        prime[j] = true;



  // N と (N + 1) / 2 が素数である要素配列を生成

  // 条件が成立すれば 1、成立しなければ 0

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

    if (!prime[i] && !prime[(i + 1) >> 1])

      count[i] = 1;



  // 累積和を生成

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

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



  scanf("%d", &N);

  while (N --) {

    scanf("%d%d", &L, &R);

    printf("%d\n", count[R] - count[L - 1]);

  }



  return 0;

}
// Slower C++ solution:
// https://atcoder.jp/contests/abc084/tasks/abc084_d

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define REP(i, n) FOR(i, 0, n)

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

#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)

#define ALL(obj) (obj).begin(), (obj).end()

#define ALLR(obj) (obj).rbegin(), (obj).rend()



// constexprな素数列挙(エラトステネスの篩)

// https://259-momone.hatenablog.com/entry/2018/05/06/015026

template <int_fast64_t max_N> struct Prime {

    bool sieve[max_N];

    constexpr Prime() : sieve() {

        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) {

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

                sieve[j] = false;

        }

    }

};



// BIT(Binary-Indexed-Tree) 別名：Fenwick Tree

template <typename T> struct BIT {

    int n;

    vector<T> d;

    BIT(int n = 0) : n(n), d(n + 1) {}

    // 要素iにxを加算

    void add(int i, T x = 1) {

        for (i++; i <= n; i += i & -i) {

            d[i] += x;

        }

    }

    // 区間[0, i]の合計を求める（閉区間）

    T sum(int i) {

        T x = 0;

        for (i++; i; i -= i & -i) {

            x += d[i];

        }

        return x;

    }

    // 区間[l, r]の合計を求める（閉区間）

    T sum(int l, int r) { return sum(r - 1) - sum(l - 1); }

};



const int SZ = 1e5 + 1;

signed main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    constexpr auto p = Prime<SZ>();

    BIT<int> bit(SZ);

    for (int i = 1; i < SZ; i += 2) {

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

            bit.add(i, 1);

        }

    }

    int Q;

    cin >> Q;

    while (Q--) {

        int l, r;

        cin >> l >> r;

        cout << bit.sum(l, r + 1) << endl;

    }



    return 0;

}


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

using namespace std;

const int SZ = 1e5 + 1;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);



    int q;

    cin >> q;

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

    int high = 0;

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

        cin >> l[i] >> r[i];

        high = max(high, r[i]);

    }



    bitset<SZ> prime;

    prime.flip();

    prime[0] = false;

    prime[1] = false;

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

        if (prime[i]) {

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

                prime[j] = false;

            }

        }

    }



    vector<int> cnt(high + 1);

    cnt[0] = 0;

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

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

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

            cnt[i]++;

        }

    }



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

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

    }

    return 0;

}
// Slower C++ solution:
// https://atcoder.jp/contests/abc084/tasks/abc084_d

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define REP(i, n) FOR(i, 0, n)

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

#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)

#define ALL(obj) (obj).begin(), (obj).end()

#define ALLR(obj) (obj).rbegin(), (obj).rend()



// constexprな素数列挙(エラトステネスの篩)

// https://259-momone.hatenablog.com/entry/2018/05/06/015026

template <int_fast64_t max_N> struct Prime {

    bool sieve[max_N];

    constexpr Prime() : sieve() {

        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) {

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

                sieve[j] = false;

        }

    }

};



// BIT(Binary-Indexed-Tree) 別名：Fenwick Tree

class BIT {

  public:

    vector<int> bit;

    int M;



    BIT(int M) : bit(vector<int>(M + 1, 0)), M(M) {}



    int sum(int i) {

        if (!i)

            return 0;

        return bit[i] + sum(i - (i & -i));

    }



    void add(int i, int x) {

        if (i > M)

            return;

        bit[i] += x;

        add(i + (i & -i), x);

    }

};



const int SZ = 1e5 + 1;

signed main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    constexpr auto p = Prime<SZ>();

    BIT bit(SZ);

    for (int i = 1; i < SZ; i += 2) {

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

            bit.add(i, 1);

        }

    }

    int Q;

    cin >> Q;

    while (Q--) {

        int l, r;

        cin >> l >> r;

        cout << bit.sum(r) - bit.sum(l - 1) << endl;

    }



    return 0;

}


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

using namespace std;

const int SZ = 1e5 + 1;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);



    int q;

    cin >> q;

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

    int high = 0;

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

        cin >> l[i] >> r[i];

        high = max(high, r[i]);

    }



    bitset<SZ> prime;

    prime.flip();

    prime[0] = false;

    prime[1] = false;

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

        if (prime[i]) {

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

                prime[j] = false;

            }

        }

    }



    vector<int> cnt(high + 1);

    cnt[0] = 0;

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

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

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

            cnt[i]++;

        }

    }



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

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

    }

    return 0;

}