#include <iostream>
#include <fstream>

using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");

#define ll long long
#define ull unsigned long long
#define pb push_back
const ll NMax = 1e12 + 5;
const int valMax = 1e6 + 5;
const int sqMax = 320;

ll T,A,B,nrPrimes,nrDivs;
int primes[valMax],divs[valMax];
bool notPrime[valMax];

int main() {

    primes[++nrPrimes] = 2;
    for (int i=3;i <= valMax;i += 2) {
        if (notPrime[i]) {
            continue;
        }

        primes[++nrPrimes] = i;
        for (int j=3*i;j <= valMax;j += 2*i) {
            notPrime[j] = true;
        }
    }

    in>>T;
    while (T--) {
        in>>A>>B;

        nrDivs = 0;
        ll p;
        for (int i=1;(p = primes[i]) != 0 && p*p <= B;++i) {
            if (B % p != 0) {
                continue;
            }

            divs[++nrDivs] = p;
            while (B % p == 0) {
                B /= p;
            }
        }
        if (B != 1) {
            divs[++nrDivs] = B;
        }

        ll lim = 1<<nrDivs, ans = 0;
        for (ll i=1;i < lim;++i) {

            ll prod = 1,nr = 0;
            for (int j=1;j <= nrDivs;++j) {
                if ((i & (1<<(j-1))) == 0) {
                    continue;
                }

                ++nr;
                prod *= divs[j];
            }
            if (nr % 2 == 1) {
                nr = A/prod;
            }
            else {
                nr = -A/prod;
            }

            ans += nr;
        }

        ans = A - ans;
        out<<ans<<'\n';
    }

    in.close();out.close();
    return 0;
}