#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;

ll gcd(ll a, ll b) {
    while (b != 0) {
        ll t = b;
        b = a % b;
        a = t;
    }
    return a;
}

vector<ll> getPrimesUpTo(ll n) {
    vector<ll> primes;
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

ll countMultiples(ll n, ll prime) {
    return n / prime;
}

ll countNotDivisibleByPrimes(ll n, const vector<ll>& primes) {
    ll count = n;
    int m = primes.size();
    for (int i = 1; i < (1 << m); ++i) {
        ll product = 1;
        int bits = __builtin_popcount(i);
        for (int j = 0; j < m; ++j) {
            if (i & (1 << j)) {
                if (product > n / primes[j]) {
                    product = n + 1;
                    break;
                }
                product *= primes[j];
            }
        }
        if (product <= n) {
            if (bits % 2 == 1) {
                count -= n / product;
            } else {
                count += n / product;
            }
        }
    }
    return count;
}

ll solve(ll A, ll B) {
    if (A > B) swap(A, B);
    vector<ll> primes = getPrimesUpTo(B);
    return countNotDivisibleByPrimes(B, primes) - countNotDivisibleByPrimes(A - 1, primes);
}

int main() {
    ifstream infile("pinex.in");
    ofstream outfile("pinex.out");

    int T;
    infile >> T;

    while (T--) {
        ll A, B;
        infile >> A >> B;
        outfile << solve(A, B) << endl;
    }

    infile.close();
    outfile.close();

    return 0;
}