10539

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

const long long PEND = 1e6;      // 質數範圍 (10^6)
const long long UPPER_LIMIT = 1e12; // 幾乎質數最大範圍 (10^12)

bitset<PEND> isp;
vector<long long> ps;            // 質數列表
vector<long long> almost_primes; // 幾乎質數列表

// 線性篩法建質數表
void pbuide() {
    isp.set();
    isp[0] = isp[1] = 0;
    for (long long i = 2; i < PEND; i++) {
        if (isp[i]) ps.push_back(i);
        for (auto &p : ps) {
            if (i * p >= PEND) break;
            isp[i * p] = 0;
            if (i % p == 0) break;
        }
    }
}

// 生成所有幾乎質數 (p^k)，確保不超過 10^12
void generate_almost_primes() {
    for (long long p : ps) {
        long long x = p * p; // 幾乎質數最小為 p^2
        while (x <= UPPER_LIMIT) {
            almost_primes.push_back(x);
            x *= p;
        }
    }
    sort(almost_primes.begin(), almost_primes.end()); // 排序以利二分搜尋
}

// 計算 [low, high] 內的幾乎質數數量
int count_almost_primes(long long low, long long high) {
    return upper_bound(almost_primes.begin(), almost_primes.end(), high) -
           lower_bound(almost_primes.begin(), almost_primes.end(), low);
}

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

    pbuide();                  // 建立質數表
    generate_almost_primes();  // 生成幾乎質數

    int n;
    cin >> n;
    while (n--) {
        long long a, b;
        cin >> a >> b;
        cout << count_almost_primes(a, b) << "\n";
    }

    return 0;
}