#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

long long A,B,M,k,Sol,N;
bool Prim[1000005];
int P[100000],Produs[100],F[100],x[100];
void Ciur()
{
    for(int i=2;i<=1000005;i++)
            if(!Prim[i])
            {
                P[++k]=i;
                for(int j=i+i;j<=1000005;j+=i)
                    Prim[j]=1;
            }
}

void Read()
{
    fin>>A>>B;
}


void Back(int k)
{
    for(int i=x[k-1]+1;i<=N;i++)
        {
            x[k]=i;
            Produs[k]=Produs[k-1]*F[i];

            if(k%2)
                Sol-=A/Produs[k];
            else
                Sol+=A/Produs[k];

            if(k<N)
                Back(k+1);
        }
}

void Solve()
{
    N=0;
    for(int i=1;P[i]*P[i]<=B;i++)
        {
            int e=0;
            while(B%P[i]==0)
                {
                    e++;
                    B=B/P[i];
                }
            if(e)
                F[++N]=P[i];
        }
    if(B>1)
        F[++N]=B;

    Sol=A;
    Produs[0]=1;
    Back(1);

}

void Print()
{
    fout<<Sol<<"\n";
}

int main()
{
    Ciur();

    fin>>M;
    while(M--)
    {
        Read();
        Solve();
        Print();
    }
    return 0;
}