#include <bits/stdc++.h>
using namespace std;
#define nMax 1000000
bool prim[nMax];

long long a,b,n,d,t,prime[1000000],nr_prime,fact[50],nr,prod,sol;
inline void ciur()
{
    prim[1]=1;
    for(int i=2;i<nMax;i++)
        if(prim[i] == 0)
            for(int j=2;i*j<nMax;j++)
                prim[i*j] = 1;
    for(int i=2;i<nMax;i++)
        if(prim[i] == 0)
            prime[++nr_prime] = i;

}
void date()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
}

int main()
{
    date();
    scanf("%lld",&n);
    ciur();

    while(n--)
    {
        scanf("%lld %lld",&a,&b);
        // descompunem in factori primi
        t=0; d=0;
        while(b>1)
        {
            d++;
            if(b%prime[d] == 0)
            {
                fact[++t] = prime[d];
                while(b%prime[d] == 0)
                    b=b/prime[d];
            }
            if(prime[d] > sqrt(b) && b>1){
                fact[++t] = b;
                b=1;

            }
        }
        sol = a;
        for(int i=1;i<(1<<t);i++)
        {
            nr =0; prod=1;
            for(int j=0;j<t;j++)
                if((1<<j) & i)
            {
                    prod = 1LL * prod*fact[j+1];
                    nr++;
            }
            if(nr%2==1)nr=-1;
            else nr =1;

        sol = sol + 1LL*nr*a/prod;
    }

    printf("%lld\n",sol);


    }
    return 0;
}