#include<cstdio>
#include<cmath>
#define MAX 1e6 +1
using namespace std;
int n,NR,nr;
long long A,B,factp[300],fact[200010];
bool viz[1000010];

long long  solve(long long a,long long b ){
    NR=0;
    int X=sqrt(double(b));
    int d=1;
    while(fact[d]<=X&&b!=1){
        if(b%fact[d]==0){
            factp[++NR]=fact[d];
            while(b%fact[d]==0){
                b/=fact[d];
            }
        }
        d++;
    }
    if(b!=1) factp[++NR]=b;
    long long sol=0,P;
    int nrb;
    for(int i=1;i<(1<<NR);++i){
        nrb=0;P=1;
        for(int j=0;j<NR;++j)
            if((1<<j)&i){
                ++nrb;
                P=P*factp[j+1];
            }
        if(nrb%2==1)sol=sol+a/P;
        else sol=sol-a/P;
    }
    return a-sol;
}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    for(int i=2;i<=MAX;++i){
        if(!viz[i]){
            fact[++nr]=i;
            for(int j=2;i*j<=MAX;j++)
                viz[i*j]=1;
        }
    }
    scanf ("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&A,&B);
        printf("%lld\n",solve(A,B));
    }
}