#include <iostream>
#include <vector>
using namespace std;
 
const int X = 10000000;
 
vector<bool> is_prime(X, true);
vector<int> prime_count(X, 0);
 
void sito() {
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < X; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < X; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = 1; i < X; ++i) {
        prime_count[i] = prime_count[i - 1] + (is_prime[i] ? 1 : 0);
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    sito();
    int n;
    cin >> n;
    int a, b;
    for (int i = 0; i < n; ++i) {
        cin >> a >> b;
        cout << prime_count[b] - prime_count[a - 1] << "\n";
    }
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IFggPSAxMDAwMDAwMDsKCnZlY3Rvcjxib29sPiBpc19wcmltZShYLCB0cnVlKTsKdmVjdG9yPGludD4gcHJpbWVfY291bnQoWCwgMCk7Cgp2b2lkIHNpdG8oKSB7CiAgICBpc19wcmltZVswXSA9IGlzX3ByaW1lWzFdID0gZmFsc2U7CiAgICBmb3IgKGludCBpID0gMjsgaSAqIGkgPCBYOyBpKyspIHsKICAgICAgICBpZiAoaXNfcHJpbWVbaV0pIHsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IGkgKiBpOyBqIDwgWDsgaiArPSBpKSB7CiAgICAgICAgICAgICAgICBpc19wcmltZVtqXSA9IGZhbHNlOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgZm9yIChpbnQgaSA9IDE7IGkgPCBYOyArK2kpIHsKICAgICAgICBwcmltZV9jb3VudFtpXSA9IHByaW1lX2NvdW50W2kgLSAxXSArIChpc19wcmltZVtpXSA/IDEgOiAwKTsKICAgIH0KfQoKaW50IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKDApOwogICAgc2l0bygpOwogICAgaW50IG47CiAgICBjaW4gPj4gbjsKICAgIGludCBhLCBiOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgICAgICBjaW4gPj4gYSA+PiBiOwogICAgICAgIGNvdXQgPDwgcHJpbWVfY291bnRbYl0gLSBwcmltZV9jb3VudFthIC0gMV0gPDwgIlxuIjsKICAgIH0KCiAgICByZXR1cm4gMDsKfQ==

MgoxNyAyNwo4IDMz

2
17 27
8 33