#include <fstream>
#define N 1000005
#define M 50
using namespace std;
int n;
int primeNumbers[N];
int factArray[M];
char sieve[N];
int divI[M];

ifstream f("pinex.in");
ofstream g("pinex.out");

void factor(int nr) {
    int i = 1;
    factArray[0] = 0;
    while(nr != 1) {
        int tot = 0;
        while((nr % primeNumbers[i]) == 0) {
            tot++;
            nr = nr / primeNumbers[i];
        }
        if (tot) factArray[++factArray[0]] = primeNumbers[i];
        if ((nr != 1) && (nr < primeNumbers[i] * primeNumbers[i])) {
            factArray[++factArray[0]] = nr;
            nr = 1;
        }
        i++;
    }
}
int backtrack() {
    divI[1]++;
    int i = 1;
    int sum1 = 0;
    while(divI[i] > 1) {
        divI[i] = 0;
        divI[i + 1]++;
        i++;
    }
    for(int i = 1; i <= factArray[0]; i++)
        sum1 += divI[i];
    return sum1;
}
void initback() {
    for(int i = 1; i <= factArray[0] + 1; i++)
     divI[i] = 0;
}
int query(int l, int r) {
    int howM;
    howM = -1;
    factor(r);
    initback();
    int total = 0;
    while(1) {
        if(howM == factArray[0]) break;
        howM = backtrack();
        int prod = 1;
        for(int i = 1; i <= factArray[0]; i++)
         if(divI[i] != 0)
           prod = prod * factArray[i];
        int pInt = l / prod;
        if(howM % 2 == 0)
            total -= pInt;
        else
            total += pInt;
    }
    return l - total;
}

int precomp() {
    for(long long i = 2; i <= N; i++) {
        if (sieve[i] == 0) {
            primeNumbers[++primeNumbers[0]] = i;
            for(long long j = i * i; j <= N; j += i)
             sieve[j] = 1;
        }
    }
}

int main()
{
    precomp();
    f >> n;
    for(int i = 1; i <= n; i++) {
        int a, b;
        f >> a >> b;
        g << query(a, b) << "\n";
    }
    return 0;
}