#include <bits/stdc++.h>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long v[15],l,A,B,M,i,j,nr,p,sol;
bool ciur[1000002];
long long prime [200000],n;
int main()
{   f>>M;
    for (i=2;i<=1000001;i++)
        if (!ciur[i])
        {   prime[++n]=i;
            for (j=i*i;j<=1000001;j+=i)
                ciur[j]=1;
        }
        //cout<<n<<' '<<prime[n]<<'\n';

    while (M--)
    {   f>>A>>B;
        l=0;sol=0;
        if(B%2==0){v[++l]=2;while(B%2==0)B/=2;}
        for(i=1;prime[i]*prime[i]<=B;i++)
            if (B%prime[i]==0)
            {   v[++l]=prime[i];
                while (B%prime[i]==0)
                B/=prime[i];
            }
         if (B>1)v[++l]=B;
         //for (i=1;i<=l;i++)cout<<v[i]<<' ';
         //cout<<'\n';
        for (i=1;i<(1<<l);i++)
        {   nr=0;p=1;
            for (j=0;j<l;j++)
                if (i&(1<<j)){
                        nr++;
                        p=p*v[j+1];
                }
            if (nr&1)sol+=A/p;
            else sol-=A/p;

        }
        g<<A-sol<<'\n';
    }

    return 0;
}