#include <iostream>
#include <fstream>
#include <unordered_map>
#include <cmath>

#define ll long long
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");

const int NMax = 1e6 + 5;

ll M,A,B,nrDivs;
int primes[NMax],divs[NMax];

int main() {
    in>>M;
    while (M--) {
        in>>A>>B;
        nrDivs = 0;

        for (ll i=2;i*i <= B;++i) {
            if (B % i != 0) {
                continue;
            }

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

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

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

            ll card = 0, prod = 1;
            for (ll j=1;j <= nrDivs;++j) {
                if ( (1<<(j-1)) & i ) {
                    ++card;
                    prod *= divs[j];
                }
            }

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

            notPrime += nr;
        }

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

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