#include <bits/stdc++.h>
using namespace std;
vector<bool> primes(3000001, true);
vector<int> soDep(3000001, 0);
int sumDigits(int n) {
    int s = 0;
    while (n > 0) {
        s += n % 10;
        n /= 10;
    }
    return s;
}
void sang() {
    primes[0] = false;
    primes[1] = false;
    for (int i = 4; i <= 3000000; i += 2) primes[i] = false;
    for (int i = 3; i*i <= 3000000; i += 2)
        for (int j = i*i; j <= 3000000; j += 2*i) primes[j] = false;
    for (int i = 1; i <= 3000000; i++)
        soDep[i] = soDep[i - 1] + (primes[i] and sumDigits(i) % 5 == 0);
}
int main() {
    freopen("SPRIME.INP","r",stdin);
    freopen("SPRIME.OUT","w",stdout);
    sang();
    int t,l,r;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> l >> r;
        cout << soDep[r] - soDep[l] + (primes[l] and sumDigits(l) % 5 == 0) << '\n';
    }
    return 0;
}