#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PB push_back
#define FI first
#define SE second
#define PI pair<int,int>
#define MP make_pair
#define ALL(DATAST) DATAST.begin(), DATAST.end()
#define MOD 1000000007
#define SIZE 1000000
#define LMT 1000000
int sieve[SIZE];
int cnt[SIZE];
int ans[SIZE];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
for (ll i = 0; i < SIZE; i++)
{
cnt[i] = 0;
sieve[i] = i;
}
for (ll i = 2; i < SIZE; i++)
{
if (sieve[i] == i)
{
for (ll j = 2 * i; j < SIZE; j += i)
{
sieve[j] /= i;
cnt[j]++;
}
}
}
for (int i = 0; i < SIZE; i++)
ans[i] = (sieve[i] == 1 && cnt[i] == 2);
for (int i = 1; i < SIZE; i++)
ans[i] += ans[i - 1];
int t, l, r;
cin >> t;
while (t--)
{
cin >> l >> r;
cout << ans[r] - ans[l - 1] << endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBQQiBwdXNoX2JhY2sKI2RlZmluZSBGSSBmaXJzdAojZGVmaW5lIFNFIHNlY29uZAojZGVmaW5lIFBJIHBhaXI8aW50LGludD4KI2RlZmluZSBNUCBtYWtlX3BhaXIKI2RlZmluZSBBTEwoREFUQVNUKSBEQVRBU1QuYmVnaW4oKSwgREFUQVNULmVuZCgpCiNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKI2RlZmluZSBTSVpFIDEwMDAwMDAKI2RlZmluZSBMTVQgMTAwMDAwMAogCmludCBzaWV2ZVtTSVpFXTsKaW50IGNudFtTSVpFXTsKaW50IGFuc1tTSVpFXTsKIAppbnQgbWFpbigpCnsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsgY291dC50aWUoMCk7CiNpZm5kZWYgT05MSU5FX0pVREdFCiAgICBmcmVvcGVuKCJpbnB1dC50eHQiLCAiciIsIHN0ZGluKTsKICAgIGZyZW9wZW4oIm91dHB1dC50eHQiLCAidyIsIHN0ZG91dCk7CiNlbmRpZgogCiAKICAgIGZvciAobGwgaSA9IDA7IGkgPCBTSVpFOyBpKyspCiAgICB7CiAgICAgICAgY250W2ldID0gMDsKICAgICAgICBzaWV2ZVtpXSA9IGk7CiAgICB9CiAKICAgIGZvciAobGwgaSA9IDI7IGkgPCBTSVpFOyBpKyspCiAgICB7CiAgICAgICAgaWYgKHNpZXZlW2ldID09IGkpCiAgICAgICAgewogICAgICAgICAgICBmb3IgKGxsIGogPSAyICogaTsgaiA8IFNJWkU7IGogKz0gaSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc2lldmVbal0gLz0gaTsKICAgICAgICAgICAgICAgIGNudFtqXSsrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogCiAgICBmb3IgKGludCBpID0gMDsgaSA8IFNJWkU7IGkrKykKICAgICAgICBhbnNbaV0gPSAoc2lldmVbaV0gPT0gMSAmJiBjbnRbaV0gPT0gMik7CiAKICAgIGZvciAoaW50IGkgPSAxOyBpIDwgU0laRTsgaSsrKQogICAgICAgIGFuc1tpXSArPSBhbnNbaSAtIDFdOwogCiAKIAogCiAgICBpbnQgdCwgbCwgcjsKICAgIGNpbiA+PiB0OwogCiAgICB3aGlsZSAodC0tKQogICAgewogICAgICAgIGNpbiA+PiBsID4+IHI7CiAgICAgICAgY291dCA8PCBhbnNbcl0gLSBhbnNbbCAtIDFdIDw8IGVuZGw7CiAgICB9CiAKIAogCiAKICAgIHJldHVybiAwOwp9