#include <fstream>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int n,t,prim[90001];
long long a,b,sol,nr,p;
long long k,divv[50];
bool ciur[1000001];
int main()
{
    ciur[0]=ciur[1]=1;
    for(int i=2;i<=1000000;i++)
        if(ciur[i]==0)
           {
               prim[++k]=i;
               for(int j=2*i;j<=1000000;j+=i)
                 ciur[j]=1;
           }
    fin>>t;
    while(t--)
    {
        fin>>a>>b;
        nr=0;
        for(int d=1; d<=k&& prim[d]*prim[d]<=b; d++)
        {
            if(b%prim[d]==0)
            {
                divv[++nr]=prim[d];
                while(b%prim[d]==0)
                    b/=prim[d];
            }

        }
        if(b!=1)
            divv[++nr]=b;
        sol=a;
        for(int i=1; i<(1<<nr); i++)
        {
            k=0;
            p=1;
            for(int j=0;j<nr;j++)
            {
               if((1<<j)&i)
               {
                   p*=1ll*divv[j+1];
                   k++;
               }
            }
            if(k%2)
                sol=sol-1ll*a/p;
            else
                sol=sol+1ll*a/p;
        }
        fout<<sol<<"\n";
    }

    return 0;
}