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

using namespace std;

using ll = long long;

// Calculăm cel mai mare divizor comun
ll gcd(ll a, ll b) {
    while (b != 0) {
        ll t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// Functie pentru a număra numerele prime
ll countPrimesUpTo(ll n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (ll p = 2; p * p <= n; ++p) {
        if (is_prime[p]) {
            for (ll i = p * p; i <= n; i += p) {
                is_prime[i] = false;
            }
        }
    }
    ll count = 0;
    for (ll p = 2; p <= n; ++p) {
        if (is_prime[p]) ++count;
    }
    return count;
}

// Aplicăm principiul includerii și excluderii pentru a calcula numărul de numere prime între A și B
ll countPrimesBetween(ll A, ll B) {
    ll count = 0;
    for (ll i = A; i <= B; ++i) {
        if (gcd(i, B) == 1) {
            count++;
        }
    }
    return count;
}

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

    ll T;
    infile >> T;

    while (T--) {
        ll A, B;
        infile >> A >> B;

        if (A > B) swap(A, B);

        ll result = countPrimesBetween(A, B);
        outfile << result << endl;
    }

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

    return 0;
}