題解

#include<bits/stdc++.h>
using namespace std;
bool zs[100100]={0};
int sum[100100];
void ls(){
    zs[0]=1;
    zs[1]=1;
    for(int i=2;i<=100000;i++){
        if(!zs[i]){
            for(int j=i+i;j<=100000;j+=i){
                zs[j]=1;
            }
        }
    }
    for(int i=1;i<=100000;i++){
        sum[i]=sum[i-1];
        if(i&1){
            if(!zs[i]&&!zs[(i+1)>>1])sum[i]++;
        }
    }
}
int main(){
    ls();
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }   
    return 0;
}