#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

#define ull unsigned long long

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int M=1100005;
const int prm=100005;

ull n,a,b,i,m,j,vf,sq,q,t,g,cnt;
ull st[50],pr[prm],sum,rez;
bool ok,x[prm],p[M];

int euclid(int a,int b)
{
    int c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}

void solve(ull k)
{
    for(int q=0;q<=1;++q)
    {
        x[k]=q;
        if(k==vf)
        {
            rez=1ull;
            cnt=0;
            ok=1;
            for(int g=1;g<=k && ok;++g)
                if(x[g])
                {
                    if(a-rez>st[q])
                        rez*=st[g];
                    else
                        ok=0;
                    cnt++;
                }
            if(cnt && ok)
                if(cnt%2==1)
                    sum-=a/rez;
                else
                    sum+=a/rez;
        }
        else
            solve(k+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin >> n;
    for(i=2;i<=M;i++)
        if(!p[i])
        {
            pr[++m]=i;
            for(j=2*i;j<=M;j+=i)
                p[j]=1;
        }
    for(;n;--n)
    {
        fin >> a >> b;
        if(a<=1000)
        {
            cnt=0;
            for(i=1;i<=a;i++)
                if(euclid(i,b)==1)
                    cnt++;
            fout << cnt << '\n';
        }
        else
        {
            vf=0;
            sum=a;
            sq=sqrt(b);
            i=1;
            while(pr[i]<=b && i<prm)
            {
                if(b%pr[i]==0)
                {
                    st[++vf]=pr[i];
                    while(b%pr[i]==0)
                        b/=pr[i];
                }
                if (pr[i]>sq&&b>1)
                {
                    st[++vf]=b;
                    b=1;
                }
                i++;
            }
            if(b>1)
                st[++vf]=b;
            solve(1);
            fout << sum << '\n';
        }
    }
    return 0;
}