#include <iostream>
#include <fstream>
#include <bitset>

using namespace std;

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

unsigned long long factF[50];
bitset<50> sol;
int S;
unsigned long long D;
long long rez;
int nr;
unsigned long long tD = 1;

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

void bkt(int 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) {
    int cnt = 1;
    if(n%2 == 0) {
        factF[cnt++] = 2;
        while(n%2 == 0)
            n /= 2;
    }
    for(int i = 3; i*i <= n; i += 2) {
        if(n%i == 0) {
            factF[cnt++] = i;
            while(n%i == 0)
                n /= i;
        }
    }
    if(n > 1)
        factF[cnt++] = n;
    for(int 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;

    for(int i = 1; i <= n; i++) {

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

    }

    return 0;
}