#include <iostream>
#include <cmath>
using namespace std;
bool ok(int n) {
    if (n<=1) return false;
    if (n<=3) return true;
    if (n%2==0 || n%3==0) return false;
    for (int i=5;i*i<=n;i+=6) {
        if (n%i==0 || n%(i+2)==0)
            return false;
    }
    return true;
}
int tinh(int n) {
    int d=0;
    for (int i=1;i*i<=n;++i) {
        if (n%i==0) {
            d+=2;
            if (i*i==n) {
                d--;
            }
        }
    }
    return d;
}
int main() {
    int t;
    cin>>t;
    while (t--) {
        int a,b;
        cin>>a >>b;
        int d=0;
        for (int i=a;i<=b;++i) {
            if (ok(tinh(i))) {
                d++;
            }
        }
        cout<<d<<endl;
    }
    return 0;
}