stablegradients/pie-gem5-pairs huggingface dataset:
// 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;

        }

    }

};



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;

}


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

    }

}




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

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

	}

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

using namespace std;

#define fi           first

#define se           second

#define ll           long long

#define pb           push_back

#define mp           make_pair

#define pll          pair<ll,ll>

#define pii          pair<int,int>

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

#define READ(x)      freopen(x,"r",stdin)

#define WRITE(x)     freopen(x,"w",stdout)

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

#define isWorking()  cout<<"Wroking"<<endl

#define FOR(i,x,y)   for(int i=x; i<y; i++)

#define SORT(x)      sort(x.begin(),x.end())

#define PRINT(ok)    cout<<(ok? "YES":"NO")<<endl

#define Fast_Input   ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);

typedef vector<int> VI;

const ll mod= 1e9+7,INF=1e18,mx= 1e5,mn=100;

int testCase=1,cas=0;



bool flag[mx+5];



void seive() {



    for(int i=2; i<=mx; i++)  flag[i]=1;



    int val=sqrt(mx)+1;

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

        if(flag[i])

            for(int j=i; j*i<=mx; j++)

                flag[i*j]=0;

}



vector <int> Like;



int main() {

    seive();



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

        int k= (i+1)/2;

        if(flag[i] && flag[k]){

            Like.push_back(i);

        }

    }



    scanf("%d",&testCase);



    while(testCase--) {

        int l,r;

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

        int a= lower_bound(all(Like),l)-Like.begin();

        int b= lower_bound(all(Like),r)-Like.begin();

        if(Like[b]==r) b++;

        printf("%d\n",b-a);

    }

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

using namespace std;

int jishu[100001],qian[100001];

int zs(int a){//输入一个数a，运行完毕后在数组里有小于a的质数，返回小于a的质数的个数 

	int sum=0;

	int i,j;

	for(i=2;i<=sqrt(a);i++){

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

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

			jishu[j]=0;

		} 

	}

	return sum;

}

int main(){

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

	zs(100000);

	jishu[1]=0;

	int n;

	cin>>n;

	qian[1]=0;

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

		if(jishu[i]&&jishu[(i+1)/2])

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

		else

			qian[i]=qian[i-1];

	}

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

		int a,b;

		scanf("%d%d",&a,&b);

		printf("%d\n",qian[b]-qian[a-1]);

	}

	return 0;

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

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 4;

int prime[N];

int cond[N];

int cumu[N];

void Fill()

{

    memset(prime,1,sizeof(prime));

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

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

    {

        if(prime[i])

        {

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

            {

                prime[j] = 0;

            }

        }

    }

}

void build()

{

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

    {

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

        {

            cond[i] = 1;

        }else

        {

            cond[i] = 0;

        }

    }



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

    {

        if(i == 0)

        {

            cumu[i] = cond[i];

        }else

        {

            cumu[i] = cumu[i - 1] + cond[i];

        }

    }



}

int main()

{

    Fill();

    build();

    int q , l , r;

    cin >> q;





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

    {

        cin >> l >> r;

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

    }

    return 0;

}


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

using namespace std;

int jishu[100001],qian[100001];

int zs(int a){//输入一个数a，运行完毕后在数组里有小于a的质数，返回小于a的质数的个数 

	int sum=0;

	int i,j;

	for(i=2;i<=sqrt(a);i++){

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

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

			jishu[j]=0;

		} 

	}

	return sum;

}

int main(){

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

	zs(100000);

	jishu[1]=0;

	int n;

	cin>>n;

	qian[1]=0;

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

		if(jishu[i]&&jishu[(i+1)/2])

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

		else

			qian[i]=qian[i-1];

	}

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

		int a,b;

		scanf("%d%d",&a,&b);

		printf("%d\n",qian[b]-qian[a-1]);

	}

	return 0;

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

  }

}

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

  }

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

#include <iostream>



using namespace std;



template <size_t N>

struct Ans

{

    bool is_prime[N];

    int count[N + 1];

    constexpr Ans() : is_prime(), count()

    {

        for (size_t i = 0; i < N; i++)

        {

            is_prime[i] = true;

        }

        is_prime[0] = false;

        is_prime[1] = false;

        for (size_t i = 2; i * i < N; i++)

        {

            if (is_prime[i])

            {

                size_t cur = i * 2;

                while (cur < N)

                {

                    is_prime[cur] = false;

                    cur += i;

                }

            }

        }



        count[0] = 0;

        for (size_t i = 0; i < N; i++)

        {

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

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

            {

                count[i + 1] += 1;

            }

        }

    }

};



int main()

{

    constexpr auto is_prime = Ans<100010>();

    int q;

    cin >> q;

    for (size_t i = 0; i < q; i++)

    {

        int a, b;

        cin >> a >> b;

        cout << (is_prime.count[b + 1] - is_prime.count[a]) << endl;

    }

}

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



using namespace std;



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    int ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

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

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

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

        {

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

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

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    constexpr auto M = 100000;

    constexpr auto solver = Solver<M>();

    int Q;

    scanf("%d", &Q);

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

    {

        int l, r;

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

        auto ans = solver.ans[r] - solver.ans[l - 1];

        printf("%d\n", ans);

    }

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



using namespace std;



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    int ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

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

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

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

        {

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

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

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    constexpr auto M = 100000;

    constexpr auto solver = Solver<M>();

    int Q;

    cin >> Q;

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

    {

        int l, r;

        cin >> l >> r;

        cout << (solver.ans[r] - solver.ans[l - 1]) << endl;

    }

}


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



using namespace std;



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    int ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

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

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

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

        {

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

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

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    constexpr auto M = 100000;

    constexpr auto solver = Solver<M>();

    int Q;

    scanf("%d", &Q);

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

    {

        int l, r;

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

        auto ans = solver.ans[r] - solver.ans[l - 1];

        printf("%d\n", ans);

    }

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

#include <iostream>



using namespace std;



template <size_t N>

struct Ans

{

    bool is_prime[N];

    int count[N + 1];

    constexpr Ans() : is_prime(), count()

    {

        for (size_t i = 0; i < N; i++)

        {

            is_prime[i] = true;

        }

        is_prime[0] = false;

        is_prime[1] = false;

        for (size_t i = 2; i * i < N; i++)

        {

            if (is_prime[i])

            {

                size_t cur = i * 2;

                while (cur < N)

                {

                    is_prime[cur] = false;

                    cur += i;

                }

            }

        }



        count[0] = 0;

        for (size_t i = 0; i < N; i++)

        {

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

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

            {

                count[i + 1] += 1;

            }

        }

    }

};



int main()

{

    constexpr auto is_prime = Ans<100010>();

    int q;

    cin >> q;

    for (size_t i = 0; i < q; i++)

    {

        int a, b;

        cin >> a >> b;

        cout << (is_prime.count[b + 1] - is_prime.count[a]) << endl;

    }

}

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



using namespace std;



int parse_int()

{

    int n = 0, c;

    while (1)

    {

        c = getchar_unlocked();

        if ('0' <= c && c <= '9')

            n = n * 10 + c - '0';

        else

            break;

    }

    return n;

}



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    int ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

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

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

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

        {

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

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

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    constexpr auto M = 100000;

    constexpr auto solver = Solver<M>();

    int Q = parse_int();

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

    {

        int l = parse_int();

        int r = parse_int();

        auto ans = solver.ans[r] - solver.ans[l - 1];

        printf("%d\n", ans);

    }

}