#include <iostream>
#include <vector>

using namespace std;

const int N = 100100;
int arr[N];
int prfs[N];

int main() {
    arr[0]=arr[1]=1;
    int cnt = 0;
    for (int i=2; i<N; ++i) {
        if (arr[i] == 0) {
            if (arr[(i+1)/2] == 0) cnt++;
            for (int d=i+i; d<N; d+=i) {
                arr[d] = 1;
            }
        }
        prfs[i] = cnt;
    }

    // for (int i=0;i<20;++i) {
    //     cout << prfs[i] << " ";
    // } cout << endl;
    // for (int i=0;i<20;++i) {
    //     cout << arr[i] << " ";
    // } cout << endl;

    int q; cin >> q;
    for (int i=0; i<q; ++i) {
        int l, r; cin >> l >> r;
        cout << prfs[r]-prfs[l-1] << endl;
    }

    return {};
}
