#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

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

#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define pb push_back
#define mp make_pair
const int NMax = 5e2 + 5;
const ll inf = 1e18 + 5;
const ll valMax = 1e6 + 5;
using zint = short;

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

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

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

    /*
    for (int i=1;i <= 21;++i) {
        cout<<primes[i]<<' ';
    }
    cout<<'\n';
    //*/

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

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

            while (B % p == 0) {
                B /= p;
            }

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

        /*
        for (int i=1;i <= nrDivs;++i) {
            cout<<divs[i]<<' ';
        }
        cout<<'\n';
        //*/

        ll lim = 1<<nrDivs, cardinalReuniune = 0;
        for (ll mask = 1; mask < lim;++mask) {
            ll prod = 1, nr = 0;
            for (int i=1;i <= nrDivs;++i) {
                if ((mask>>(i-1)) & 1) {
                    prod *= divs[i];
                    ++nr;
                }
            }

            nr = (nr % 2) ? A/prod : -A/prod;
            cardinalReuniune += nr;
        }

        out<<A - cardinalReuniune<<'\n';
    }

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