#include <iostream>
#include <fstream>
#include <deque>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");

const int NMax = 2e5 + 5;
const int sqMax = 1e6 + 5;
const int inf = 1e9 + 5;
using zint = short;

ll T;
ll primes[sqMax],divs[sqMax];
bool notPrime[sqMax];

int main() {

    primes[++primes[0]] = 2;
    for (ll i=3;i <= sqMax;i += 2) {
        if (notPrime[i]) {
            continue;
        }

        primes[++primes[0]] = i;
        for (ll j=3*i;j <= sqMax;j += 2*i) {
            notPrime[j] = true;
        }
    }

    in>>T;
    while (T--) {
        ll A,B;
        in>>A>>B;
        divs[0] = 0;

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

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

            divs[++divs[0]] = p;
        }
        if (temp != 1) {
            divs[++divs[0]] = temp;
        }

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

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


            ll card = A/prod;
            if (nr % 2 == 0) {
                card = -card;
            }

            //cout<<mask<<' '<<nr<<' '<<prod<<' '<<card<<'\n';
            ans += card;
        }
        //cout<<'\n';

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

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