// https://szkopul.edu.pl/problemset/problem/GfNdWdsmfgHxoByl0ETuZW9c/site/?key=statement

// Liczby kompletne

#include <bits/stdc++.h>

constexpr int MAX_SIEVE = 18000000;
std::vector<int> primes;
std::vector<char> is_prime;
std::vector<int> complete_nums;

void sieve() {
    primes.reserve(1200000);
    is_prime.assign(MAX_SIEVE + 1, 1);
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i * i <= MAX_SIEVE; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAX_SIEVE; j += i)
                is_prime[j] = 0;
        }
    }
    for (int i = 2; i <= MAX_SIEVE; i++) {
        if (is_prime[i]) primes.push_back(i);
    }
}

inline void check_and_add(long long n, long long min_val, long long max_val) {
    if (n >= min_val && n <= max_val) {
        complete_nums.push_back((int)n);
    }
}

void generate_complete_numbers() {
    complete_nums.reserve(19000000);

    // D=1
    check_and_add(1, 1, 9);

    // D=2 (p)
    for (int p : primes) {
        if (p >= 10 && p <= 99) complete_nums.push_back(p);
        if (p > 99) break;
    }

    // D=3 (p^2)
    for (long long p : primes) {
        long long val = p * p;
        if (val > 999) break;
        check_and_add(val, 100, 999);
    }

    // D=4 (p^3, p*q)
    long long min4 = 1000, max4 = 9999;
    for (long long p : primes) {
        long long val = p * p * p;
        if (val > max4) break;
        check_and_add(val, min4, max4);
    }
    for (size_t i = 0; i < primes.size(); i++) {
        long long p = primes[i];
        if (p * p >= max4) break;
        for (size_t j = i + 1; j < primes.size(); j++) {
            long long val = p * primes[j];
            if (val > max4) break;
            check_and_add(val, min4, max4);
        }
    }

    // D=5 (p^4)
    for (long long p : primes) {
        long long val = p * p;
        val *= val;
        if (val > 99999) break;
        check_and_add(val, 10000, 99999);
    }

    // D=6 (p^5, p^2*q)
    long long min6 = 100000, max6 = 999999;
    for (long long p : primes) {
        long long val = p * p;
        val *= val;
        val *= p;
        if (val > max6) break;
        check_and_add(val, min6, max6);
    }
    for (size_t i = 0; i < primes.size(); i++) {
        long long p = primes[i];
        long long p2 = p * p;
        if (p2 * 2 > max6) break;
        for (size_t j = 0; j < primes.size(); j++) {
            if (i == j) continue;
            long long val = p2 * primes[j];
            if (val > max6) break;
            check_and_add(val, min6, max6);
        }
    }

    // D=7 (p^6)
    for (long long p : primes) {
        long long p2 = p * p;
        long long val = p2 * p2 * p2;
        if (val > 9999999) break;
        check_and_add(val, 1000000, 9999999);
    }

    sort(complete_nums.begin(), complete_nums.end());

    // === D = 8 (NAJTRUDNIEJSZY PRZYPADEK) ===

    long long min8 = 10000000, max8 = 99999999;
    long long size8 = max8 - min8 + 1;
    std::vector<char> marked(size8, 0);

    // p^7
    for (long long p : primes) {
        long long val = p;
        for (int k = 0; k < 6; k++)
            val *= p;
        if (val > max8) break;
        if (val >= min8) marked[val - min8] = 1;
    }
    // p^3 * q
    for (size_t i = 0; i < primes.size(); i++) {
        long long p = primes[i];
        long long p3 = p * p * p;
        if (p3 * 2 > max8) break;
        for (size_t j = 0; j < primes.size(); j++) {
            if (i == j) continue;
            long long val = p3 * primes[j];
            if (val > max8) break;
            if (val >= min8) marked[val - min8] = 1;
        }
    }
    // p * q * r (Główna pętla)
    for (size_t i = 0; i < primes.size(); i++) {
        long long p = primes[i];
        if (p * p * p > max8) break;

        for (size_t j = i + 1; j < primes.size(); j++) {
            long long q = primes[j];
            long long pq = p * q;
            if (pq * q > max8) break;

            long long max_r = max8 / pq;
            long long min_r = std::max((long long)q + 1, (min8 + pq - 1) / pq);

            if (min_r > max_r) continue;

            auto it = lower_bound(primes.begin() + j + 1, primes.end(), min_r);

            while (it != primes.end()) {
                long long r = *it;
                if (r > max_r) break;
                marked[(pq * r) - min8] = 1;
                ++it;
            }
        }
    }

    for (int i = 0; i < size8; i++) {
        if (marked[i]) {
            complete_nums.push_back(min8 + i);
        }
    }
    std::vector<char>().swap(marked);

    // === D = 9 (Mała liczba przypadków) ===
    long long min9 = 100000000, max9 = 999999999;
    size_t start_segment = complete_nums.size();

    // p^8
    for (long long p : primes) {
        long long val = p;
        for (int k = 0; k < 7; k++)
            val *= p;
        if (val > max9) break;
        check_and_add(val, min9, max9);
    }
    // p^2 * q^2
    for (size_t i = 0; i < primes.size(); i++) {
        long long p = primes[i];
        if (p * p * p * p > max9) break;
        for (size_t j = i + 1; j < primes.size(); j++) {
            long long q = primes[j];
            long long pq = p * q;
            long long val = pq * pq;
            if (val > max9) break;
            check_and_add(val, min9, max9);
        }
    }
    // Sortujemy tylko końcówkę (D=9)
    sort(complete_nums.begin() + start_segment, complete_nums.end());
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    sieve();
    generate_complete_numbers();

    int t;
    if (std::cin >> t) {
        while (t--) {
            int a, b;
            std::cin >> a >> b;
            // Binary search na wynikowym wektorze
            auto it1 = lower_bound(complete_nums.begin(), complete_nums.end(), a);
            auto it2 = upper_bound(complete_nums.begin(), complete_nums.end(), b);
            std::cout << (it2 - it1) << "\n";
        }
    }

    return 0;
}