#include<bits/stdc++.h>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int XMAX=1000005;

int m,primes[XMAX],fact[30];
long long A,B,sol;
bitset<XMAX>viz;

void Ciur()
{
    int i;
    long long j;
    primes[++primes[0]]=2;
    for (i=3;i<XMAX;i+=2)
        if (!viz[i])
        {
            primes[++primes[0]]=i;
            for (j=1LL*i*i;j<XMAX;j+=i) viz[j]=1;
        }
}

int main()
{
    int i,conf,n,cnt;
    long long aux;
    fin>>m;
    Ciur();
    while (m--)
    {
        fin>>A>>B;
        n=0;
        for (i=1;i<=primes[0] && 1LL*primes[i]*primes[i]<=B;i++)
            if (B%primes[i]==0)
            {
                fact[++n]=primes[i];
                while (B%primes[i]==0) B/=primes[i];
            }
        if (B>1) fact[++n]=B;

        sol=A;
        for (conf=1;conf<(1<<n);conf++)
        {
            cnt=0;aux=1;
            for (i=0;i<n;i++)
                if (conf&(1<<i))
                    cnt++,aux=1LL*aux*fact[i+1];
            if (cnt&1) sol-=A/aux;
            else sol+=A/aux;
        }

        fout<<sol<<"\n";
    }
    return 0;
}