#include <fstream>
#define ll long long
using namespace std;
ll a,b,i,n,fact[1000005],j;
bool ok[1000005];
int divid(ll a,ll x)
{
    while (a%x==0) a/=x;
    return a;
}
int solve(int A,int B)
{
    int x[1000005],i;
    ll prod,p,fp=0,cb=B,sum=0,k,t=0;
    for (i=0; i<=1000004; i++) x[i]=0;
    while (cb>1)
        {fp++;
        if (cb%fact[fp]==0) x[++t]=fact[fp],cb=divid(cb,fact[fp]);}
    for (i=1; i<(1<<t); i++)
    {
        ll ci=i;
        p=-1;prod=1;k=0;
        while (ci>0)
        {
            p++;
            if (ci%2==1) prod*=x[p+1],k++;
            ci/=2;
        }
        if (k%2==0) sum-=(a/prod);
        else sum+=(a/prod);
    }
    return sum;
}
int main()
{
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    f>>n;int tix=1000000;
    for (i=2; i<=tix; i++) ok[i]=true;
    for (i=2; i<=tix; i++)
    {
        if (ok[i]==true) {fact[++fact[0]]=i;
        for (j=2*i; j<=tix; j+=i) ok[j]=false;}
    }
    for (i=1; i<=n; i++)
    {
        f>>a>>b;
        g<<a-solve(a,b)<<'\n';
    }
    f.close();
    g.close();
    return 0;
}