#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define nmax 100000
bool ciur[nmax];
long long m,a,b,cnt,prim[10005];
int main()
{
    prim[++cnt]=2;
    for(int i=4;i<=nmax;i+=2)
        ciur[i]=1;
    for(int i=3;i<=nmax;i+=2)
    {
        if(ciur[i]==0)
        {
           prim[++cnt]=i;
           for(int j=i+i;j<=nmax;j+=i)
                    ciur[j]=1;
        }
    }

    fin>>m;
    while(m--)
    {
        fin>>a>>b;
        int i=1,nrd=0,v[105];
        while(b>1 && prim[i]*prim[i]<=b)
        {
           if(b%prim[i]==0)
           {
               v[++nrd]=prim[i];
               while(b%prim[i]==0)
                b/=prim[i];
           }
           ++i;
        }
        if(b>1)v[++nrd]=b;
        int rez=a;
        for(i=1;i<(1LL<<nrd);++i)
        {
            int p=1,nel=0;
            for(int j=0;j<nrd;++j)
            {
                if(i&(1LL<<j))
                {
                    ++nel;
                    p*=v[j+1];
                }
            }
            if(nel%2)
                rez-=a/p;
            else
                rez+=a/p;
        }
        fout<<rez<<'\n';
    }
    return 0;
}