#include <bits/stdc++.h>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");


long long cmmdc(long long a,long long b)
{
    long long c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}


long long m,pas,a,n,d,i,nr,produs,rez,j,sol,b,v[1010];

int main()
{
    f>>m;
    for(int pas=1;pas<=m;pas++)
    {
        f>>a>>b;

        sol=0;
        n=0;
        d=2;
        while(d*d<=b)
        {
            if(b%d==0)
            {

                n++;
                v[n]=d;
                while(b%d==0)b=b/d;
            }
            d++;
        }

        if(b!=1){n++;v[n]=b;}


        for(i=1;i<(1<<n);i++)
        {
            nr=0;
            produs=1;
            rez=0;


            for(j=0;j<n;j++)
            {
                if((i&(1<<j))!=0)
                {
                    nr++;
                    produs=produs*v[j+1];
                    rez=cmmdc(rez,v[j+1]);
                }
            }
            if(nr!=1)rez=produs/rez;
            else rez=produs;


            if(nr%2==1){sol=sol+a/rez;}
            else sol=sol-a/rez;
        }
        g<<a-sol<<'\n';
    }
    return 0;
}