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

using namespace std;

int const N=1e5;

int prime[N];

int ans[N];

int main() {

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

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

        prime[i]=1;

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

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

{

    if(prime[i]==1)

    {

        //cout<<i;

        for(long long  j=i*i;j<=N;j+=i)

        {



            //cout<<j;

         prime[j]=0;

        }

    }

}



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

{

   int  x=(i+1)/2;

    if(prime[i]&&prime[x])

    {

       // prime[i]=1;

       ans[i]=1;

   // cout<<"yes";

    }

    else

        ans[i]=0;

   // cout<<i;

}



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

{

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

}



int q;

cin>>q;

while(q--)

{

    int l,r;

    cin>>l>>r;



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

using namespace std;

int const N=1e5;

int prime[N];

int ans[N];

int main() {

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

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

        prime[i]=1;

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

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

{

    if(prime[i]==1)

    {

        //cout<<i;

        for(long long  j=i*i;j<=N;j+=i)

        {



            //cout<<j;

         prime[j]=0;

        }

    }

}



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

{

   int  x=(i+1)/2;

    if(prime[i]&&prime[x])

    {

       // prime[i]=1;

       ans[i]=1;

   // cout<<"yes";

    }

    else

        ans[i]=0;

   // cout<<i;

}



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

{

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

}



int q;

cin>>q;

while(q--)

{

    int l,r;

    cin>>l>>r;



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

}

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

using namespace std;

vector <bool> prim;

vector <int> vec;

vector <int>::iterator it;

vector <int>::iterator it1;

void prime()

{

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

        prim.push_back(true);

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

    {

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

            prim[j]=false;

    }

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

    {

        int x=(i+1)/2;

        if(prim[i] == true && prim[x] == true)

        {

            vec.push_back(i);

            //cout<<"not"<<endl;

        }



    }

}

int main()

{

    prime();

    //cout<<vec[0]<<endl;

    int q;

    int l,r;

    cin>>q;

    while(q--)

    {

        cin>>l>>r;

        it = lower_bound(vec.begin(),vec.end(),l);

        it1 = upper_bound(vec.begin(),vec.end(),r);

        int pos1=it-vec.begin();

        //cout<<pos1<<endl;

        int pos2 = it1-vec.begin();

        //cout<<pos2<<endl;

        cout<<pos2-pos1<<endl;

    }

    return 0;

}


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

using namespace std;

int const N=1e5;

int prime[N];

int ans[N];

int main() {

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

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

        prime[i]=1;

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

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

{

    if(prime[i]==1)

    {

        //cout<<i;

        for(long long  j=i*i;j<=N;j+=i)

        {



            //cout<<j;

         prime[j]=0;

        }

    }

}



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

{

   int  x=(i+1)/2;

    if(prime[i]&&prime[x])

    {

       // prime[i]=1;

       ans[i]=1;

   // cout<<"yes";

    }

    else

        ans[i]=0;

   // cout<<i;

}



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

{

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

}



int q;

cin>>q;

while(q--)

{

    int l,r;

    cin>>l>>r;



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

}

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

using namespace std;

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

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

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

#define FORR(i, m, n) for(int i = m; i >= n; i--)

#define SORT(v, n) sort(v, v+n);

#define VSORT(v) sort(v.begin(), v.end());

 

using ll = long long;

using vll = vector<ll>;

using vvll = vector<vector<ll>>;

using P = pair<ll, ll>;



vll Eratosthenes(ll N){

    vll a(N + 1, 1);

  	for(ll i = 0; i < N; i++){

		a[i] = 1;

	}

	for(ll i = 2; i < sqrt(N); i++){

		if(a[i]){

			for(ll j = 0; i * (j + 2) < N; j++){

				a[i *(j + 2)] = 0;

			}

		}

	}

    a[0] = a[1] = 0;

    return a;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    ll q;

    cin >> q;

    ll l, r;



    vll isprime = Eratosthenes(1e5 + 10);

    vll sss(1e5 + 11);

    REP(i, 1e5 + 10){

        if(i == 0) continue;

        sss[i] = sss[i - 1] + isprime[i] * isprime[(i + 1) / 2];

    }

    while(q){

        cin >> l >> r;

        ll res = sss[r] - sss[l - 1];

        cout << res << endl;

        q--;

    }

    return 0;

}

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

using namespace std;

int const N=1e5;

int prime[N];

int ans[N];

int main() {

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

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

        prime[i]=1;

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

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

{

    if(prime[i]==1)

    {

        //cout<<i;

        for(long long  j=i*i;j<=N;j+=i)

        {



            //cout<<j;

         prime[j]=0;

        }

    }

}



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

{

   int  x=(i+1)/2;

    if(prime[i]&&prime[x])

    {

       // prime[i]=1;

       ans[i]=1;

   // cout<<"yes";

    }

    else

        ans[i]=0;

   // cout<<i;

}



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

{

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

}



int q;

cin>>q;

while(q--)

{

    int l,r;

    cin>>l>>r;



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

}

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

using namespace std;





bool mark[100005];



void sieve()

{

    int sz = 100000;

    mark[1] = true;

    mark[0] = true;



    for (int i=4; i<=sz; i+=2)    mark[i] = true;



    for (int p=3; p<=sz; p+=2)

    {

        if (mark[p] == false)

        {

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

            {

                mark[i] = true;

            }

        }

    }

}



int cnt[100005];



int main(){



    memset(mark, 0, sizeof(mark));



    sieve();



    memset(cnt, 0, sizeof(cnt));



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



        int x = i;

        int y = (i+1)/2;



        if(mark[x] == false && mark[y] == false) cnt[i] = 1;

        else cnt[i] = 0;

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







    }



    int q;



    scanf("%d", &q);



    while(q--){



        int x, y;



        scanf("%d %d", &x, &y);



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





    }



    return 0;





    return 0;

}


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

using namespace std;

const int N=1e5+5;

int A[N],n,cnt,q,mx,mn,x,y,z;

bitset<N> isprime;

bool prime(int l){

    if(l<=1) return 0;

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

        if(l%i==0) return 0;

    return 1;

}

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

    isprime.set();

    sieve();

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

     A[i]=(isprime[i]&&isprime[(i+1)/2]);

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

    }

    //for(int i=0;i<55;++i)

      //  cout<<i<<":"<<A[i]<<endl;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d",&x,&y);

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

    }

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

using namespace std;

const int N=1e5+5;

int A[N],n,cnt,q,mx,mn,x,y,z;

bitset<N> isprime;

bool prime(int l){

    if(l<=1) return 0;

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

        if(l%i==0) return 0;

    return 1;

}

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

    isprime.set();

    sieve();

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

     A[i]=(isprime[i]&&isprime[(i+1)/2]);

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

    }

    //for(int i=0;i<55;++i)

      //  cout<<i<<":"<<A[i]<<endl;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d",&x,&y);

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

    }

    return 0;

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

using namespace std;

#define mx 100010

int a[mx],p[mx],k,koko[mx];



void sieve()

{

    a[1]=1;

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

    {

        if(!a[i])

        {

            p[k++]=i;

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

            {

                a[j]=1;

            }

        }

    }

}



int main()

{

    sieve();

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

    {

        if(!a[i] && !a[(i+1)/2]) koko[i]=koko[i-1]+1;

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

    }

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int l,r;

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

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

    }

}


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

using namespace std;

const int N=1e5+5;

int A[N],n,cnt,q,mx,mn,x,y,z;

bitset<N> isprime;

bool prime(int l){

    if(l<=1) return 0;

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

        if(l%i==0) return 0;

    return 1;

}

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

    isprime.set();

    sieve();

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

     A[i]=(isprime[i]&&isprime[(i+1)/2]);

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

    }

    //for(int i=0;i<55;++i)

      //  cout<<i<<":"<<A[i]<<endl;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d",&x,&y);

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

    }

    return 0;

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

using namespace std;



#define ll      long long

#define MAX     100007

#define inf     99999999999999

#define MOD     1000000007

#define pii     pair<int,int>

#define FIN     freopen("input.txt","r",stdin);

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



int nprime;

bool mark[MAX];



void sieve (void)

{

    long long i,j,lim=sqrt(MAX*1.0)+2;

    mark[0]=mark[1]=1;

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

        mark[i]=1;

    for(i=3;i<=lim;i+=2)

    {

        if(!mark[i])

        {

            for(j=i*i;j<=MAX;j+=2*i)

                mark[j]=1;

        }

    }

}

ll q,l,r,res[MAX];

void pre()

{

    for(ll i=1;i<MAX;i+=2)

    {

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

        {

            res[i]++;

        }

    }

    for(ll i=1;i<MAX;i++)

    {

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

    }

}

int main ()

{

    sieve();

    pre();

    scanf("%lld",&q);

    while(q--)

    {

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

        printf("%lld\n",res[r]-res[l-1]);

    }

}




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

using namespace std;

const int N=1e5+5;

int A[N],n,cnt,q,mx,mn,x,y,z;

bitset<N> isprime;

bool prime(int l){

    if(l<=1) return 0;

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

        if(l%i==0) return 0;

    return 1;

}

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

    isprime.set();

    sieve();

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

     A[i]=(isprime[i]&&isprime[(i+1)/2]);

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

    }

    //for(int i=0;i<55;++i)

      //  cout<<i<<":"<<A[i]<<endl;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d",&x,&y);

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

    }

    return 0;

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

using namespace std;







int isPrime[100019], okay[100019], cum[100019];

void sieve()

{



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

        isPrime[i]=1;



     isPrime[2]=0;



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

    {

        if(isPrime[i]==0)

        {

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

                okay[i]=1;



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

            {

                isPrime[i*j]=1;

            }



        }

    }



    isPrime[1]=1;





//    for(int i=1; i<=10; i++)

//    {

//        if(okay[i]==1)

//        {

//            printf("%d\n",i);

//        }

//    }









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

    {

        cum[i]= cum[i-1]+okay[i];

       // printf("%d\n",cum[i]);

    }









}



int main()

{



    sieve();



    int q,l,r;

    scanf("%d",&q);





    while(q--)

    {

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



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







    }





}






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

using namespace std;

const int N=1e5+5;

int A[N],n,cnt,q,mx,mn,x,y,z;

bitset<N> isprime;

bool prime(int l){

    if(l<=1) return 0;

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

        if(l%i==0) return 0;

    return 1;

}

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

    isprime.set();

    sieve();

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

     A[i]=(isprime[i]&&isprime[(i+1)/2]);

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

    }

    //for(int i=0;i<55;++i)

      //  cout<<i<<":"<<A[i]<<endl;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d",&x,&y);

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

    }

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

using namespace std;

const int N=1e5+5;

int A[N],n,cnt,q,mx,mn,x,y,z;

bitset<N> isprime;

bool prime(int l){

    if(l<=1) return 0;

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

        if(l%i==0) return 0;

    return 1;

}

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

    isprime.set();

    sieve();

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

     A[i]=(isprime[i]&&isprime[(i+1)/2]);

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

    }

    //for(int i=0;i<55;++i)

      //  cout<<i<<":"<<A[i]<<endl;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d",&x,&y);

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

    }

    return 0;

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

using namespace std;



const int MAXN = 1e5 + 10;

bool isp[MAXN];

int n, ps[MAXN];



int main() {

	isp[1] = 1;

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

		if (!isp[i])

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

				isp[j] = 1;

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

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

			ps[i]++;

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

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

	cin >> n;

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

		int l, r;

		cin >> l >> r;

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

	}

}

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

using namespace std;

const int N=1e5+5;

int A[N],n,cnt,q,mx,mn,x,y,z;

bitset<N> isprime;

bool prime(int l){

    if(l<=1) return 0;

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

        if(l%i==0) return 0;

    return 1;

}

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

    isprime.set();

    sieve();

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

     A[i]=(isprime[i]&&isprime[(i+1)/2]);

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

    }

    //for(int i=0;i<55;++i)

      //  cout<<i<<":"<<A[i]<<endl;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d",&x,&y);

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

    }

    return 0;

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

using namespace std;

vector <bool> prim;

vector <int> vec;

vector <int>::iterator it;

vector <int>::iterator it1;

void prime()

{

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

        prim.push_back(true);

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

    {

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

            prim[j]=false;

    }

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

    {

        int x=(i+1)/2;

        if(prim[i] == true && prim[x] == true)

        {

            vec.push_back(i);

            //cout<<"not"<<endl;

        }



    }

}

int main()

{

    prime();

    //cout<<vec[0]<<endl;

    int q;

    int l,r;

    cin>>q;

    while(q--)

    {

        cin>>l>>r;

        it = lower_bound(vec.begin(),vec.end(),l);

        it1 = upper_bound(vec.begin(),vec.end(),r);

        int pos1=it-vec.begin();

        //cout<<pos1<<endl;

        int pos2 = it1-vec.begin();

        //cout<<pos2<<endl;

        cout<<pos2-pos1<<endl;

    }

    return 0;

}


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

using namespace std;

const int N=1e5+5;

int A[N],n,cnt,q,mx,mn,x,y,z;

bitset<N> isprime;

bool prime(int l){

    if(l<=1) return 0;

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

        if(l%i==0) return 0;

    return 1;

}

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

    isprime.set();

    sieve();

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

     A[i]=(isprime[i]&&isprime[(i+1)/2]);

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

    }

    //for(int i=0;i<55;++i)

      //  cout<<i<<":"<<A[i]<<endl;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d",&x,&y);

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

    }

    return 0;

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



using namespace std ;



const int MAX = 1e5 + 10 ;



int prime[MAX] , ans[MAX];



int main()

{

	ios_base::sync_with_stdio(0) ;

	cin.tie(0) ;

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

		prime[i] = 1 ; 

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

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

	{

		if(prime[i])

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

				prime[j] = 0 ;

	}

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

	{

		ans[i] = ans[i-1] + (bool)(prime[i] && prime[(i+1)/2]);

	}

	int q ;

	cin>>q ;

	while(q--)

	{

		int l , r ;

		cin>>l>>r ;

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

	}

	return 0 ;

}

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

using namespace std;

const int N=1e5+5;

int A[N],n,cnt,q,mx,mn,x,y,z;

bitset<N> isprime;

bool prime(int l){

    if(l<=1) return 0;

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

        if(l%i==0) return 0;

    return 1;

}

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

    isprime.set();

    sieve();

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

     A[i]=(isprime[i]&&isprime[(i+1)/2]);

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

    }

    //for(int i=0;i<55;++i)

      //  cout<<i<<":"<<A[i]<<endl;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d",&x,&y);

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

    }

    return 0;

}