#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>
#define MAXPRIM 100001
using namespace std;

int n,m;
bitset<MAXPRIM> isprime;
vector <int> primes;

void sieve() {
    for (size_t i=2; i<MAXPRIM; i++)
        if (isprime[i])
            for (size_t j =i; j*i<MAXPRIM; j++)
                isprime[j*i]=0;
}

int main() {
    int i,j,bc,nr;
    long long a,b,res,p,l;
    isprime.set();
    sieve();
    for (i=2; i<MAXPRIM; i++)
     if (isprime[i])
        primes.push_back(i);

    ifstream in("pinex.in");
    ofstream out("pinex.out");
    in>>m;
    for (i=1; i<=m; i++) {
        in>>a>>b;
        bc=b;
        res=0;
        vector <int> divs;
        for (j=0; primes[j]<=sqrt((double)b);j++)
            if (!(bc%primes[j])) {
                divs.push_back(primes[j]);
                while (!(bc%primes[j]))
                    bc/=primes[j];
            }

        if (bc!=1)
            divs.push_back(bc);

        for (j=1; j<(1 << (divs.size())); j++) {
            p=1;
            nr=0;
            n=1;
            for (l=0; l< divs.size(); l++)
                if ( (1 << l) & j) {
                    nr++;
                    p*=divs[l];
                }

            if (!(nr%2))
                n=-1;

            res+= n*(a/p);

        }

        res=a-res;

        out<<res<<'\n';
    }

    out.close();
    return 0;
}