#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long n, a, b, i, j, v[502], nrd, r;

static inline void Divi(long long b) {
    nrd = 0;

    if(b % 2 == 0) v[++nrd] = 2;
    while(b % 2 == 0) b >>= 1;

    int d = 3;
    while(d * d <= b) {
        if(b % d == 0) v[++nrd] = d;
        while(b % d == 0) b /= d;

        d += 2;
    }
    if(b > 1) v[++nrd] = b;
}

int main() {
    fin >> n;
    while(n--) {
        fin >> a >> b;
        Divi(b);

        r = 0;
        for(i = 1; i < (1 << nrd); i++) {
            long long prod = 1;

            for(j = 1; j <= nrd; j++) {
                if((i >> (j - 1)) & 1) prod *= v[j];
            }

            if(__builtin_popcount(i) % 2 == 1) r += (a / prod);
            else r -= (a / prod);
        }
        fout << a - r << "\n";
    }

    return 0;
}