#include <bits/stdc++.h>

using namespace std;

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

const int nmax=1000001;
int prim[100000];
bool ciur[nmax];
int t,a,b,k,n;
int v[150];
long long rez,nrc,p;

int main()
{
    ciur[0]=1;
    ciur[1]=1;
    for(int i=2;i*i<=nmax;i++)
    {
        if(!ciur[i])
        {
            prim[++k]=i;
            for(int j=2;j<=nmax/i;j++)
                ciur[i*j]=1;
        }
    }

    f>>t;
    while(t--)
    {
        f>>a>>b;
        n=0;
        int j=1;
        while(b>1&&prim[j]*prim[j]<=b)
        {
            if(b%prim[j]==0)
            {
                v[++n]=prim[j];
                while(b%prim[j]==0)b=b/prim[j];
            }
            j++;

        }
        if(b>1)n++;
        v[n]=b;
        rez=a;
        for(int i=1;i<(1LL<<n);i++)
        {
            nrc=0;
            p=1;
            for(int j=0;j<n;j++)
            {
                if(i&(1LL<<j))
                {
                    nrc++;
                    p=p*v[j+1];
                }
            }
            if(nrc%2==1)rez-=a/p;
            else rez+=a/p;
        }
        g<<rez<<'\n';
    }


    return 0;
}