#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL,LL> per;
typedef long double LD;


const LL N=1000005;
const LL M=1005;
const LL mod=1000000007;
const LL inf=(1<<30);
const LL linf=(1LL<<61);

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

LL m,nr,l,s,lim,prime[N],fact[M];
bool ciur[N],sub[M];
LL a,b,rez,t;

void submultime(LL x)
{
    t=1LL;
    for(LL i=1;i<=l;++i)
    {
        if(x%2) sub[i]=1, ++nr, t*=fact[i];
        else sub[i]=0;
        x/=2;
    }
}

LL baga()
{
    if(nr%2) return (a/t);
    else return (-a/t);
}

void Eratosthenes()
{
    ciur[1]=1;
    LL H=N-5;
    for(LL i=2;i<=H;++i)
    {
        if(!ciur[i])
        {
            prime[++s]=i;
            for(LL j=2;i*j<=H;++j) ciur[i*j]=1;
        }
    }
}

int main()
{
    f>>m; ++m;
    Eratosthenes();
    while(--m)
    {
        f>>a>>b;
        t=sqrt(b); l=0LL;
        for(LL i=1;i<=s && b!=1;++i) if(b%prime[i]==0)
        {
            fact[++l]=prime[i];
            while(b%prime[i]==0) b/=prime[i];
        }
        lim=(1<<l)-1; rez=0LL;
        for(LL i=1;i<=lim;++i)
        {
            nr=0;
            submultime(i);
            rez+=baga();
        }
        g<<(a-rez)<<'\n';
    }
    return 0;
}