#include <bits/stdc++.h>
///M=500
///A=10^18
///B=10^12
using namespace std;
///
long long m, a, b, i, j, k, x, sol, v;
bool ciur[1000000];
long long primelist[1000000], primeone[1000000];
///
void buildCiur();
int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    scanf("%lld", &m);
    buildCiur();
    while(m--){
        scanf("%lld%lld", &a, &b);
        sol=0;
        int total=0, div;
        for(i=1; i<=v; ++i) {
            if(1LL*primelist[i]*primelist[i]>b) break;
            if(!(b%primelist[i])) {
                primeone[++total]=primelist[i];
                while(!(b%primelist[i])) b/=primelist[i];
            }
        }
        if(b>1) primeone[++total]=b;
        for(i=1; i<(1<<total); ++i){
            long long c=i; div=1; int pm=0;
            for(j=1; j<=total; ++j){
                if(c&1) {div=1LL*div*primeone[j]; pm^=1;}
                c>>=1;
            }
            sol+=(a/div);
            if(!pm) sol-=2*(a/div);
        }
        printf("%lld\n", a-sol);
    }
    return 0;
}
void buildCiur(){
    for(int i=2; i<1000000; ++i){
        if(ciur[i]) continue;
        primelist[++v]=i;
        for(int j=i+i; j<1000000; j+=i) ciur[j]=true;
    }
}