#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000;
vector<int> special;

void init() {
    // Thêm số 3^8
    special.push_back(6561);

    // Sàng nguyên tố
    const int LIM = 333; // 9 * 333^2 > 10^6
    vector<bool> isprime(LIM + 1, true);
    isprime[0] = isprime[1] = false;
    for (int i = 2; i * i <= LIM; i++) {
        if (isprime[i]) {
            for (int j = i * i; j <= LIM; j += i)
                isprime[j] = false;
        }
    }

    // Tạo các số 9 * p^2
    for (int p = 2; p <= LIM; p++) {
        if (p != 3 && isprime[p]) {
            long long n = 9LL * p * p;
            if (n <= MAXN) special.push_back(n);
        }
    }

    sort(special.begin(), special.end());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Nếu cần đọc file
    // freopen("SDB.INP", "r", stdin);
    // freopen("SDB.OUT", "w", stdout);

    init();

    int T;
    cin >> T;
    while (T--) {
        long long a, b;
        cin >> a >> b;
        auto L = lower_bound(special.begin(), special.end(), a);
        auto R = upper_bound(special.begin(), special.end(), b);
        cout << (R - L) << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define el '\n'
#define all(x) x.begin(), x.end()
typedef long long ll;
const int MOD = 1e9 + 7;

const int maxN = (int) 1e6 + 7;

bool ok[maxN];
int pre[maxN];
ll spe = 6561; // 3^8

// Sàng nguyên tố
void snt(){
    ok[0] = ok[1] = 1;
    for(int i = 2; i*i < maxN; i++){
        if(ok[i] == 0){
            for(int j = i*i; j < maxN; j += i) ok[j] = 1;
        }
    }

    // pre[i] lưu số lượng số nguyên tố <= i
    for(int i = 1; i < maxN; i++) pre[i] = pre[i - 1] + !ok[i];
}

ll get(ll N){
    if(N < 0) return 0;
    ll ans = 0;
    // Kiểm tra 3^8
    if(spe <= N) ans++;

    // Với 9*p^2 <= N => p^2 <= N/9 => p <= sqrt(N/9)
    // Công thức đúng là p <= sqrt(N/9)
    // Tuy nhiên code dùng sqrt(N)/3 là sai lệch nhỏ nhưng về bản chất p_max = floor(sqrt(N/9))
    // Code gốc dùng M = sqrt(N)/3, ta cần điều chỉnh lại cho chính xác
    // p_max = floor(sqrt(N/9))
    ll M = sqrt(N / 9.0);

    // Chỉ tính các p >= 2 và p != 3
    // pre[M] là số lượng số nguyên tố <= M
    // Nếu M >= 3, ta trừ đi 1 để loại bỏ p = 3
    ll count_p = pre[M];
    if (M >= 3) count_p--;

    ans += count_p;
    return ans;
}

void solve(){
    ll a, b;
    cin >> a >> b;
    cout << get(b) - get(a - 1) << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    snt();
    int T;
    if (cin >> T) {
        while(T--) solve();
    }
    return 0;
}

// Nguon: blablablabkabcu
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll isqrt_floor(ll x){
    if (x < 0) return -1;
    ll l = 0, r = 2000000000LL;
    while (l < r){
        ll m = (l + r + 1) >> 1;
        if (m*m <= x) l = m;
        else r = m - 1;
    }
    return l;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("SDB.inp","r",stdin);
    // freopen("SDB.OUT","w",stdout);

    int T;
    if (!(cin >> T)) return 0;
    vector<pair<long long,long long>> qs(T);
    ll maxB = 0;
    for (int i = 0; i < T; ++i){
        ll a,b; cin >> a >> b;
        qs[i] = {a,b};
        if (b > maxB) maxB = b;
    }

    // Chỉ sàng đến giới hạn cần thiết
    ll maxDiv9 = maxB / 9;
    ll limit = isqrt_floor(maxDiv9);
    if (limit < 2) limit = 2;

    // Sieve prime
    vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i * i <= limit; ++i) {
        if (is_prime[i]) {
            for (ll j = i * i; j <= limit; j += i)
                is_prime[j] = false;
        }
    }

    // Đếm số lượng số đặc biệt <= X
    // Có thể dùng prefix sum hoặc binary search
    vector<ll> special;
    if (6561 <= maxB) special.push_back(6561);
    for (ll p = 2; p <= limit; ++p) {
        if (p != 3 && is_prime[p]) {
            special.push_back(9 * p * p);
        }
    }
    sort(special.begin(), special.end());

    for (auto [a, b] : qs) {
        auto it1 = lower_bound(special.begin(), special.end(), a);
        auto it2 = upper_bound(special.begin(), special.end(), b);
        cout << (it2 - it1) << '\n';
    }
    return 0;
}