stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

	}

}


// Optimized solution to the same problem (faster):
#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;

    }



}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
// 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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
// 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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
// 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;

        }

    }

};



const int SZ = 1e5 + 1;

signed main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    constexpr auto p = Prime<SZ>();

    vector<int> cnt(SZ + 1);

    cnt[0] = 0;

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

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

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

            cnt[i]++;

        }

    }

    int Q;

    cin >> Q;

    while (Q--) {

        int l, r;

        cin >> l >> r;

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

    }



    return 0;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<iomanip>

#include<cmath>

#include<string>

#include<vector>

#include<list>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<stack>

using namespace std;

typedef long long ll;

#define fi first

#define se second

#define mp make_pair

const int inf=1e9+7;

const ll mod=1e9+7;

const ll big=1e18;



int DP[100005];

int DP1[100005];



int main() {

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

        DP[i] = 1;

    }

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

        if(DP[i] == 0) continue;

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

            DP[i*j] = 0;

        }

    }

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

        if(i%2==0) continue;

        if((DP[i]==1) & (DP[(i+1)/2]==1)) DP1[i] = 1;

    }



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

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

    }



    int Q;

    cin>>Q;

    int ans[Q];

    int l, r;

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

        cin>>l>>r;

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

    }

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

        cout<<ans[i]<<endl;

    }

}




// Optimized solution to the same problem (faster):
#include<iostream>

#include<iomanip>

#include<cmath>

#include<string>

#include<cstring>

#include<vector>

#include<list>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<stack>

using namespace std;

typedef long long ll;

#define fi first

#define se second

#define mp make_pair

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

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

const int inf=1e9+7;

const ll mod=1e9+7;

const ll mod1=998244353;

const ll big=1e18;

const double PI=2*asin(1);



int main() {

  bool prime[100005];

  bool like[100005];

  for(int i=0;i<100005;++i) prime[i] = true;

  prime[0] = false;

  prime[1] = false;

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

    if(prime[i]==false) continue;

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

      prime[i*j] = false;

    }

  }

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

    if(i%2==1 && prime[i] && prime[(i+1)/2]) like[i] = true;

    else like[i] = false;

  }

  int likenum[100005];

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

    if(like[i]) likenum[i] = 1;

    else likenum[i] = 0;

  }

  for(int i=1;i<100005;++i) likenum[i] += likenum[i-1];

  int Q;

  cin>>Q;

  int l, r;

  int ans[Q];

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

    cin>>l>>r;

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

  }

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

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



const int sz = 100001;



int q, l, r, first, second;

bool s[sz];

vector<int> p;



void siv(){

	for(int i = 4; i < sz; i += 2) s[i] = 1;

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

		if(!s[i]) {

			for(int j = i * i; j < sz; j += i + i) s[j] = 1;

		}

	}

}



int main(){

	siv();

	s[0] = s[1] = 1;

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

		if(s[i] == 0 && s[ (i + 1) / 2] == 0) p.push_back(i);

	}

	cin >> q;

	while(q--){

		cin >> l >> r;

		cout << upper_bound(p.begin(), p.end(), r) - lower_bound(p.begin(), p.end(), l) << "\n";

	}

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

typedef pair<int, int> P;

struct erato {

  vector<bool> hyou;

  int mx;

  void init() {

    hyou[1] = true;

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

      if (hyou[i] == false) continue;

      hyou[i] = true;

      for (int j = 2; j <= mx / i; j++) {

        hyou[i * j] = false;

      }

    }

  }

  erato(int x) {

    hyou.resize(x + 3, true);

    mx = x;

    init();

  }

};

const int mx = 1e5;

int main() {

  int Q;

  cin >> Q;

  erato era(mx);

  vector<ll> A(mx + 1);

  A[0] = 0;

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

    A[i] = A[i - 1];

    if (era.hyou[i] == true && era.hyou[(i + 1) / 2] && i % 2 == 1 && i != 1)

      A[i]++;

  }

  REP(i, Q) {

    int l, r;

    cin >> l >> r;

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

  }

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

typedef pair<int, int> P;

const int INF = 1e9;

bool erato[(int)1e5 + 20];

int main() {

  ll Q;

  cin >> Q;

  REP(i, (int)1e5 + 20) erato[i] = true;

  erato[0] = false;

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

    if (erato[i] != true) {

      continue;

    }

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

      erato[i * j] = false;

    }

  }

  for (int i = (int)1e5; i > 1; i--) {

    if (i % 2 == 0) {

      erato[i] = false;

      continue;

    }

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

      erato[i] = true;

    } else {

      erato[i] = false;

    }

  }

  erato[0] = false, erato[1] = false, erato[2] = false;

  vector<int> wa(1e5 + 20);

  wa[0] = 0;

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

    wa[i] = wa[i - 1] + erato[i];

  }

  REP(i, Q) {

    int l, r;

    cin >> l >> r;

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

  }

}

// Fastest known solution for this problem: