#include <bits/stdc++.h>

using namespace std;

vector <long long> primes;

int main() {
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    int M;
    scanf("%d",&M);
    while(M--) {
        long long A,B,rez=0;
        scanf("%lld%lld",&A,&B);
        while(B%2==0) {
            if(primes.empty())
                primes.push_back(2);
            B/=2;
        }
        long long d=3;
        while(d*d <= B) {
            while(B%d==0) {
                if(primes.empty() || primes.back()!=d)
                    primes.push_back(d);
                B/=d;
            }
            d+=2;
        }
        if(B>1)
            primes.push_back(B);
        for(int i=1; i < (1<<primes.size()); i++) {
            long long nr=1;
            int cate=0;
            for(int j=0; j<primes.size(); j++)
                if(i & (1 << j))
                    nr*=primes[j],cate++;
            if(cate & 1)
                rez += A/nr;
            else
                rez -= A/nr;
        }
        printf("%lld\n",A-rez);
        primes.clear();
    }
}