#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXSQRT (int)1e6
ifstream fin("pinex.in");
ofstream fout("pinex.out");
char sieve[MAXSQRT+1];
signed main() {
    sieve[0]=sieve[1]=1;
    for(int d=2; d*d<=MAXSQRT; d++) {
        if(!sieve[d]) {
            for(int i=d*d; i<=MAXSQRT; i+=d) {
                sieve[i]=1;
            }
        }
    }
    vector<int>primes;
    for(int i=0; i<=MAXSQRT; i++) {
        if(!sieve[i]) {
            primes.push_back(i);
        }
    }
    int q,a,b;
    fin>>q;
    while(q--) {
        int ans=0;
        fin>>a>>b;
        vector<int>prime_divs;
        int i=0;
        while(primes[i]*primes[i]<=b) {
            if(b%primes[i]==0) {
                prime_divs.push_back(primes[i]);
                while(b%primes[i]==0) {
                    b/=primes[i];
                }
            }
            i++;
        }
        if(b>1) {
            prime_divs.push_back(b);
        }
        int sz=prime_divs.size();
        for(int mask=0; mask<(1<<sz); mask++) {
            int prod=1,cnt=0;
            for(i=0; i<sz; i++) {
                if(mask&(1<<i)) {
                    prod*=prime_divs[i];
                    cnt++;
                }
            }
            if(cnt%2==0) {
                ans+=a/prod;
            } else {
                ans-=a/prod;
            }
        }
        fout<<ans<<'\n';
    }
    return 0;
}