#include <iostream>
#include <vector>

using namespace std;

long k,iz;
vector < long > a;
vector < long > b;

bool prime(long x) {
    if(x == 1) return false;
    for(long q = 2;q <= x / 2;q ++) {
        if(x % q == 0) return false;
    }
    return true;
}

int main() {
    cin >> k;
    a.resize(k);
    b.resize(k);
    for(long i = 0;i < k;i ++) {
        cin >> a[i] >> b[i];
    }
    for(long i = 0;i < k;i ++) {
        iz = 0;
        for(long j = a[i];j <= b[i];j ++) {
            if(prime(j)) iz ++;
        }
        cout << iz << endl;
    }
    return 0;
}