#include<fstream>
#include<bitset>
#include<cstring>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long a,sum;
long long b,p[300000],x,k,nr,c[100],i,j,n,bb;
int u[100];
bitset<1000001> f;

int main()
{
    for(i=2;i<=1000000;i++)
        if(!f[i])
        {
            p[++nr]=i;
            for(j=i+i; j<=1000000; j=j+i)
                f[j]=1;
        }
    fin>>n;
    nr=0;
    int h;
    for(h=1;h<=n;h++)
    {
        fin>>a>>b;
        nr=0;
        bb=b;
        sum=0;
        for(i=1;p[i]*p[i]<=b&&bb!=1;i++)
        {
            if(bb%p[i]==0)
            {
                c[++nr]=p[i];
                while(bb%p[i]==0)
                    bb/=p[i];
            }
        }
        if(bb!=1)
            c[++nr]=bb;
        memset(u, 0, sizeof(u));
        k=0;
        x=1;
        while (u[0]==0)
        {
            j=nr;
            while(u[j]==1)
            {
                u[j]=0;
                j--;
            }
            u[j]=1;
            if(j==0)
                break;
            k=0;
            x=1;
            for(j=1;j<=nr;j++)
            {
                k+=u[j];
                if(u[j]==1)
                x *= c[j];
            }
            if (k%2==1)
                sum+=a/x;
            else
                sum-=a/x;
        }
        if (sum>0)
            fout<<a-sum<<"\n";
        else
            fout<<a+sum<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}