#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
bool c[1000001];
int prim[100001],d;
int n,i,j,k;
long long a,b,nr,prod,fact[100011],sol,p,o;
int main()
{
    for(i=2;i<=1000000;i++)
        if(c[i]==0)
    {
        d++;
        prim[d]=i;
        for(int j=i+i;j<=1000000;j=j+i)
            c[j]=1;
    }
    f>>n;
    for(o=1;o<=n;o++)
    {
        f>>a>>b;
        d=1;
        k=0;
        while(b>1)
        {
            if(b%prim[d]==0)
            {
                k++;
                fact[k]=prim[d];
                while(b%prim[d]==0)
                    b=b/prim[d];
            }
            d++;
            if(prim[d]*prim[d]>b)
            {
                k++;
                fact[k]=b;
                b=1;
            }
        }
        sol=a;
        for(i=1;i<(1<<k);i++)
        {
            nr=0;
            prod=1;
            for(j=0;j<k;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;
        }
        g<<sol<<'\n';
    }
    return 0;
}