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

int n,m;
bitset<MAXPRIM> isprime;
vector <int> primes;
long long divs[31];

void sieve() {
    for (long long i=2; i<MAXPRIM; i++) {
        if (i==526307)
            n=1;

        if (isprime[i])
            for (long long j =i; j*i<MAXPRIM; j++) {
                isprime[j*i]=0;
                if (j*i==526307)
                    n=1;
            }
    }
}

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

    ifstream in("pinex.in");
    ofstream out("pinex.out");
    in>>m;
    for (i=1; i<=m; i++) {
        in>>a>>b;
        if (i==68)
            a=a;
        bc=b;
        res=0;
        szd=-1;
        //vector <long long> divs;

        for (j=0; j<primes.size()&&bc>1&&primes[j]<=sqrt(bc);j++) {
            if (primes[j]==526307)
                a=a;
            if (!(bc%primes[j])) {
                //divs.push_back(primes[j]);
                divs[++szd]=primes[j];
                while (!(bc%primes[j]))
                    bc/=primes[j];
            }
        }

        if (bc!=1)
            //divs.push_back(bc);
            divs[++szd]=bc;
        if (divs[0])
            szd++;

        /*j=-1;

        while(bc>1) {
            j++;
            if (!(bc%primes[j])) {
                divs[++szd] = primes[j];
                while (!(bc%primes[j]))
                    bc/=primes[j];
            }

            if (primes[j]>sqrt(bc)&&bc>1) {
                divs[++szd]=bc;
                bc=1;
            }


        }*/

        for (j=1; j<(1 << (szd)); j++) {
            p=1;
            nr=0;
            n=1;
            for (l=0; l< szd; 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;
}