#include <fstream>
#define N 10000005

using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
long long a, b, n, divs[N], prim[N];
bool ciur[N];
int m;

void ciurr()
{
    for(long long j=4;j<=N;j+=2)
        ciur[j]=1;
    prim[++prim[0]]=2;
    for(long long i=3;i<=N;i+=2)
        if(!ciur[i])
        {
            for(long long j=2*i;j<=N;j+=i)
                ciur[j]=1;
            prim[++prim[0]]=i;
        }
}

void divizori()
{
    long long nt=0, nd=1;
    while(prim[nd]*prim[nd]<=b)
    {
        if(b%prim[nd]==0)
        {
            divs[++nt]=prim[nd];
            while(b%prim[nd]==0)
                b=b/prim[nd];
        }
        nd++;
    }
    if(b>1)
        divs[++nt]=b;

    for(long long i=1;i<(1<<nt);i++)
    {
        long long nr=0, p=1;
        for(long long j=0;j<nt;j++)
            if((1<<j)&i)
                p=p*divs[j+1], nr++;
        if(nr%2==0)
            n=n-1LL*a/p;
        else
            n=n+1LL*a/p;
    }
}

int main()
{

    cin>>m;
    ciurr();
    for(int test=1;test<=m;test++)
    {
        n=0;
       cin>>a>>b;
        divizori();
        cout<<a-n<<'\n';
    }
    return 0;
}