#include <fstream>
#include <cmath>
#define max_val 1000000
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
bool notprim[max_val+100];
long long prim[max_val];
long long fact[100];
void precalc()
{
    for(int i=2; i<max_val; ++i)
        if(notprim[i]==0)
        {
            prim[++prim[0]]=i;
            for(int j=i*2; j<max_val; j+=i)
                notprim[j]=1;
        }
}

void pinex(long long a, long long b)
{
    fact[0]=0;
    for(int d=1; d<=prim[0] && b!=1; ++d)
        if(b%prim[d]==0)
        {
        fact[++fact[0]]=prim[d];
        while(b && b%prim[d]==0)
            b/=prim[d];
        }
        else if(prim[d]>sqrt(b))
            fact[++fact[0]]=b, b=1;

    int t=fact[0];
    long long prod=0, ans=a, nr=0;
    for(long long i=1; i<(1<<t); ++i)
    {
        prod=1; nr=0;
        for(long long j=0; j<t; ++j)
            if(((1<<j)&i))
                prod=prod*fact[j+1], ++nr;
        if(nr%2==0)
            nr=1;
        else nr=-1;
        ans=ans+nr*(a/prod);
    }
    cout<<ans<<'\n';
}

int main()
{
    long long T,A,B;
    precalc();
    cin>>T;
    for(int I=1; I<=T; ++I)
    {
        cin>>A>>B;
        pinex(A,B);
    }
    return 0;
}