#include <iostream>
#include <fstream>
#include <bitset>
#define MAX 1000003
#define sq 1000

using namespace std;

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

unsigned long long factF[50];
bitset<50> sol;
unsigned long long S;
unsigned long long D;
long long rez;
unsigned long long nr;
unsigned long long tD = 1;
bitset<MAX> ciur;
unsigned long long primes[100000];
int k=1;

void afis() {
    if(nr == 0)
        return;
    if(nr%2 == 1)
        rez += D/tD;
    else
        rez -= D/tD;
}

void bkt(unsigned long long top) {
    if(top == S) {
        afis();
    } else {
        sol[top] = 1;
        nr++;
        tD *= factF[top];
        bkt(top+1);
        sol[top] = 0;
        nr--;
        tD /= factF[top];
        bkt(top+1);
    }
}

void fact(unsigned long long n, unsigned long long M) {
    unsigned long long cnt = 1;
    for(int i = 1; primes[i] <= n && i < k; i++) {
        if(n%primes[i] == 0) {
            factF[cnt++] = primes[i];
            while(n%primes[i] == 0)
                n /= primes[i];
        }
    }
    if(n > 1)
        factF[cnt++] = n;
    for(unsigned long long i = 1; i <= cnt; i++)
        sol[i] = 0;
    S = cnt;
    nr = 0;
    tD = 1;
    D = M;
    rez = 0;
    bkt(1);
    out << M-rez << '\n';
}

int main() {

    unsigned long long n,a,b;
    in >> n;

    primes[k++] = 2;
    for(int i = 3; i < MAX; i += 2) {
        if(!ciur[i]) {
            primes[k++] = i;
            if(i > sq)
                continue;
            for(long long j = 1LL*i*i; j < MAX; j += i)
                ciur[j] = 1;
        }
    }

    for(unsigned long long i = 1; i <= n; i++) {

        in >> a >> b;
        fact(b, a);

    }

    return 0;
}