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

#include <vector>

#define MAX_R 100000

using namespace std;

int main(void) {

  int q;

  cin >> q;

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

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

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

  }

  vector<bool> prime(MAX_R + 1, 1);

  vector<int> count(MAX_R + 1, 0);

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

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

    if (prime[i]) {

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

        prime[j] = 0;

      }

    }

  }

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

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

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

    } else {

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

    }

  }

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

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

  }

  return 0;

}

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





#define dhai_machli ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define endl "\n"

#define ll long long

#define pii pair<int,int>

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

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

#define rep(i,a,b,c) for(int i=a; i<b; i+=c)

#define brep(i,a,b,c) for(int i=a; i>b; i-=c)

#define tc(t) int t; cin>>t; while(t--)

#define sz(v) int((v).size())

#define pb push_back



const int N = 2e5 + 10;





bool f[100001];

int c[100002];



int n, l, r;



using namespace std;



int main()

{







   dhai_machli;







   for ( int i = 2; i * 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];



      

   cin >> n;

   while (n--)

   {

      cin >> l >> r;



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

   }





   return 0;

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

#include <vector>

#define MAX_R 100000

using namespace std;

int main(void) {

  int q;

  cin >> q;

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

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

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

  }

  vector<bool> prime(MAX_R + 1, 1);

  vector<int> count(MAX_R + 1, 0);

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

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

    if (prime[i]) {

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

        prime[j] = 0;

      }

    }

  }

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

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

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

    } else {

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

    }

  }

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

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

  }

  return 0;

}

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





#define dhai_machli ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define endl "\n"

#define ll long long

#define pii pair<int,int>

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

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

#define rep(i,a,b,c) for(int i=a; i<b; i+=c)

#define brep(i,a,b,c) for(int i=a; i>b; i-=c)

#define tc(t) int t; cin>>t; while(t--)

#define sz(v) int((v).size())

#define pb push_back



const int N = 2e5 + 10;





bool f[100001];

int c[100002];



int n, l, r;



using namespace std;



int main()

{







   dhai_machli;







   for ( int i = 2; i * 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];



      

   cin >> n;

   while (n--)

   {

      cin >> l >> r;



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

   }





   return 0;

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

#include <vector>

using namespace std;



int main() {

    // エラトステネスのふるい

    int MAX = 101010;

    vector<int> is_prime(MAX, 1);

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

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

        if (!is_prime[i]) continue;

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

    }



    // 2017-like 数かどうか

    vector<int> a(MAX, 0);

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

        if (i % 2 == 0) continue;

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

    }



    // 累積和

    vector<int> s(MAX+1, 0);

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



    // クエリ処理

    int Q; 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.4265202395558068x):
#include <bits/stdc++.h>

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

using namespace std;



typedef long long ll;



int main(void)

{

    int MAX = 101000;

    vector<bool> is_prime(MAX, true);

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

    rep(i, MAX)

    {

        if(!is_prime[i]) continue;

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

    }



    vector<bool> a(MAX, false);

    rep(i, MAX)

    {

        if(i%2 == 0) continue;

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

    }



    vector<int> s(MAX+1, 0);

    rep(i, MAX)

    {

        s[i+1] = s[i];

        if(a[i]) s[i+1]++;

    }



    int q;

    cin >> q;

    rep(i, q)

    {

        int l, r;

        cin >> l >> r;

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

    }



    return 0;

}
// Slower C++ solution:
// AtCoder template

// 見た奴全員saba!

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

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



// 素数判定

// 計算量O(√n)

template<class T>

bool isPrime(T n){

    if(n < 2) return false;

    for(long long i = 2; i*i <= n; ++i) if(n % i == 0) return false;

    return true;

}





// 素数列挙

// nまでの素数をEratosthenesの篩で列挙する

// 計算量O(nloglogn)

template<class T>

vector<T> prime_list(T n){

    vector<T> ret;

    vector<T> isPrime(n+1,1);

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

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

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

        ret.push_back(i);

        for(long long j = i*i; j <= n; j += i) isPrime[j] = 0;

    }

    return ret;

    // return isPrime;  // 状況によってはこっちを返す

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    int m = 100001,q; cin >> q;



    vector<int> p = prime_list(m);

    int n = p.size();

    vector<bool> like_list(m+1,false);

    rep(i,n){

        if(isPrime((p[i]+1)/2)) like_list[p[i]] = true;

    }

    like_list[2] = false;

    vector<int> pn_sum(m+1);

    pn_sum[0] = 0;

    rep(i,m){

        if(like_list[i+1]) pn_sum[i+1] = pn_sum[i]+1;

        else pn_sum[i+1] = pn_sum[i];

    }

    

    int l,r;

    rep(i,q){

        cin >> l >> r;

        cout << pn_sum[r] - pn_sum[l-1] << "\n";

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.4145686991031405x):
// AtCoder template

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

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



template<class T>

T gcd(T a, T b){

    if(b == 0) return a;

    return gcd(b, a%b);

}



// 素数列挙

// nまでの素数をEratosthenesの篩で列挙する

// 計算量O(nloglogn)

template<class T>

vector<T> prime_list(T n){

    vector<T> ret;

    vector<T> isPrime(n+1,1);

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

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

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

        ret.push_back(i);

        for(long long j = i*i; j <= n; j += i) isPrime[j] = 0;

    }

    //return ret;

    return isPrime;  // 状況によってはこっちを返す

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    int q; cin >> q;

    vector<int> isPrime = prime_list(100001);

    vector<int> psum(100002, 0);

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

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

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

    }

    int l,r;

    rep(i,q){

        cin >> l >> r;

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

    }

}
// 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.3011686893624925x):


#include <iostream>

#include <cstdio>

#include<string>

#include<cstring>

#include <algorithm>

#include <cmath>

#include <map>



#define N 100005



using namespace std;



int vis[N],a[N];

void sushu() {

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

		if(!vis[i]) {

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

				vis[j]=1;

		}

	}

}



int main() {

	memset(vis,0,sizeof(vis));

	sushu();

	vis[1]=1;

	int sum=0,n;

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

		if(i%2==1) {

			if(vis[i]==0&&vis[(i+1)/2]==0)

				sum++;

		}

		a[i]=sum;

	}

	scanf("%d",&n);



	while(n--) {

		int c,b;

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

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

	}



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

using namespace std;

const int mx = 1e5+7;



int ara[mx],prime[mx],cnt[mx];



void sievesolve()

{

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

    {

        if(ara[i]== 0)

        {

            prime[i] = 1;

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

                ara[j] = 1;

        }

    }

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

    {

        if(prime[i] and prime[(i+1)/2]) cnt[i] = 1;

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

    }

}



int main()

{

    sievesolve();

    int t;

    cin >> t;

    while(t--)

    {

        int a , b;

        cin >> a >> b;

        cout << cnt[b] - cnt[a-1] << endl;

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2100572723163094x):


#include <iostream>

#include <cstdio>

#include<string>

#include<cstring>

#include <algorithm>

#include <cmath>

#include <map>



#define N 100005



using namespace std;



int vis[N],a[N];

void sushu() {

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

		if(!vis[i]) {

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

				vis[j]=1;

		}

	}

}



int main() {

	memset(vis,0,sizeof(vis));

	sushu();

	vis[1]=1;

	int sum=0,n;

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

		if(i%2==1) {

			if(vis[i]==0&&vis[(i+1)/2]==0)

				sum++;

		}

		a[i]=sum;

	}

	scanf("%d",&n);



	while(n--) {

		int c,b;

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

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

	}



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

using namespace std;



using VS = vector<string>;    using LL = long long;

using VI = vector<int>;       using VVI = vector<VI>;

using PII = pair<int, int>;   using PLL = pair<LL, LL>;

using VL = vector<LL>;        using VVL = vector<VL>;



#define ALL(a)  begin((a)),end((a))

#define RALL(a) (a).rbegin(), (a).rend()

#define PB push_back

#define EB emplace_back

#define MP make_pair

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

#define SORT(c) sort(ALL((c)))

#define RSORT(c) sort(RALL((c)))

#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)

#define debug(x) cerr << #x << ": " << x << endl

const int INF = 1e9;                          const LL LINF = 1e16;

const LL MOD = 1000000007;                    const double PI = acos(-1.0);

int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };



/* -----  2018/02/23  Problem: 084_abc_d / Link: https://abc084.contest.atcoder.jp/tasks/abc084_d?lang=en  ----- */

/* ------問題------



「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。

Q 個のクエリが与えられます。

クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。



-----問題ここまで----- */

/* -----解説等-----



素数表ができれば後は適当に2017っぽい数がわかるので累積和をとれば十分高速。



----解説ここまで---- */



LL N;



LL ans = 0LL;

#define primeN 100000

bool prime[primeN + 1];// 外部だとハッシュ表みたいになる

void make_prime() {

	FOR(i, 0, primeN + 1) {

		prime[i] = 1;

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



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

		if (prime[i]) {

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

				prime[j] = 0;

		}

	}

}

#undef primeN 



int main() {

	cin.tie(0);

	ios_base::sync_with_stdio(false);



	make_prime();



	VI like2017(100001, 0);

	FOR(i, 1, 100001) {

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

			like2017[i] = 1;

		}

	}

	VI sum(100002, 0);

	FOR(i, 0, 100001) {

		sum[i + 1] += sum[i]+ like2017[i];

	}



	cin >> N;

	FOR(i, 0, N) {

		int L, R;

		cin >> L >> R;

		cout << sum[R+1] - sum[L] << endl;

	}



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1495275542918468x):


#include <iostream>

#include <cstdio>

#include<string>

#include<cstring>

#include <algorithm>

#include <cmath>

#include <map>



#define N 100005



using namespace std;



int vis[N],a[N];

void sushu() {

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

		if(!vis[i]) {

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

				vis[j]=1;

		}

	}

}



int main() {

	memset(vis,0,sizeof(vis));

	sushu();

	vis[1]=1;

	int sum=0,n;

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

		if(i%2==1) {

			if(vis[i]==0&&vis[(i+1)/2]==0)

				sum++;

		}

		a[i]=sum;

	}

	scanf("%d",&n);



	while(n--) {

		int c,b;

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

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

	}



}
// 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.3717262716863223x):
#include <iostream>

#include <bits/stdc++.h>

using namespace std;



#define pb push_back

#define F first

#define S second

#define fo(i,a,b)  for(int i = a; i < b; i++)



using ll = long long;

using ld = long double;

using ul = unsigned long long;

using ii = pair<int, int>;

#define Mosta     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define ReadFile            freopen("input.in","r",stdin)

#define WriteFile           freopen("output.txt","w",stdout)

const ll mod7 = 1000000007,mod = 1000000000,OO = 0x3f3f3f3f;

const ld EPS = 1e-7;

double Pi=acos(-1);

const ld rad=Pi/180.0;

ll power(ll x, ll y, ll p)

{

    ll res = 1;

    while (y > 0)

    {

        if (y & 1)

            res = (res*x) % p;

        y = y>>1;

        x = (x*x) % p;

    }

    return res;

}

ll nCr (ll n,ll m)

{

        return(m == 0)?1:n*nCr(n-1,m-1)/m;

}

/*****************************************************/



const int N = (int) 1e5 + 5;



bool prime[N];



int ans[N];



int main()

{

    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;

        }

    }



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

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

            ans[i]++;

    }



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

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



    int q;

    cin >> q;



    while(q--){

        int l , r;

        cin >> l >> r;

        cout << ans[r] - ans[l-1] << "\n";

    }



    return 0;

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

using namespace std;

const int mx = 1e5+7;



int ara[mx],prime[mx],cnt[mx];



void sievesolve()

{

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

    {

        if(ara[i]== 0)

        {

            prime[i] = 1;

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

                ara[j] = 1;

        }

    }

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

    {

        if(prime[i] and prime[(i+1)/2]) cnt[i] = 1;

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

    }

}



int main()

{

    sievesolve();

    int t;

    cin >> t;

    while(t--)

    {

        int a , b;

        cin >> a >> b;

        cout << cnt[b] - cnt[a-1] << endl;

    }

    return 0;

}


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

#include <bits/stdc++.h>

using namespace std;



#define pb push_back

#define F first

#define S second

#define fo(i,a,b)  for(int i = a; i < b; i++)



using ll = long long;

using ld = long double;

using ul = unsigned long long;

using ii = pair<int, int>;

#define Mosta     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define ReadFile            freopen("input.in","r",stdin)

#define WriteFile           freopen("output.txt","w",stdout)

const ll mod7 = 1000000007,mod = 1000000000,OO = 0x3f3f3f3f;

const ld EPS = 1e-7;

double Pi=acos(-1);

const ld rad=Pi/180.0;

ll power(ll x, ll y, ll p)

{

    ll res = 1;

    while (y > 0)

    {

        if (y & 1)

            res = (res*x) % p;

        y = y>>1;

        x = (x*x) % p;

    }

    return res;

}

ll nCr (ll n,ll m)

{

        return(m == 0)?1:n*nCr(n-1,m-1)/m;

}

/*****************************************************/



const int N = (int) 1e5 + 5;



bool prime[N];



int ans[N];



int main()

{

    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;

        }

    }



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

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

            ans[i]++;

    }



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

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



    int q;

    cin >> q;



    while(q--){

        int l , r;

        cin >> l >> r;

        cout << ans[r] - ans[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.6589842104156778x):
#include <bits/stdc++.h>

using namespace std;

const int n=1e5+10;

bitset<n> isprime;

vector<int>answer;

void sieve()

{

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

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

        if(isprime[p])

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

                isprime[m]=0;



}





int the2017ers[n];

void is2017()

{

    int sum=0;

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

    {

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

        the2017ers[p]=sum;



    }



}



int main()

{

     ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    isprime.set();

    sieve();

    is2017();

    int tc,l,r;

    cin>>tc;

    while(tc--)

    {

        cin>>l>>r;

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

    }





    return 0;

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

using namespace std;

const int mx = 1e5+7;



int ara[mx],prime[mx],cnt[mx];



void sievesolve()

{

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

    {

        if(ara[i]== 0)

        {

            prime[i] = 1;

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

                ara[j] = 1;

        }

    }

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

    {

        if(prime[i] and prime[(i+1)/2]) cnt[i] = 1;

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

    }

}



int main()

{

    sievesolve();

    int t;

    cin >> t;

    while(t--)

    {

        int a , b;

        cin >> a >> b;

        cout << cnt[b] - cnt[a-1] << endl;

    }

    return 0;

}


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

using namespace std;

const int n=1e5+10;

bitset<n> isprime;

vector<int>answer;

void sieve()

{

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

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

        if(isprime[p])

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

                isprime[m]=0;



}





int the2017ers[n];

void is2017()

{

    int sum=0;

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

    {

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

        the2017ers[p]=sum;



    }



}



int main()

{

     ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    isprime.set();

    sieve();

    is2017();

    int tc,l,r;

    cin>>tc;

    while(tc--)

    {

        cin>>l>>r;

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

    }





    return 0;

}