#include <fstream>
#include <bitset>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
const int N=1000009;
bitset <N+1> ciur;
long long prime[80000],cook[10],nr;
void desc(long long n)
{
    int d=1;
    nr=0;
    while(prime[d]*prime[d]<=n)
    {
        if(n%prime[d]==0)
        {
            cook[++nr]=prime[d];
            while(n%prime[d]==0)
                n/=prime[d];
        }
        d++;
    }
    if(n!=1)
        cook[++nr]=n;
}
int main()
{
    long long n,i,cnt=1,d,a,b,numar,cate,j,k;
    in>>n;
    prime[1]=2;
    for(i=4; i<=N; i+=2)
        ciur[i]=1;
    for(i=3; i*i<=N; i+=2)
        if(ciur[i]==0)
        {
            prime[++cnt]=i;
            for(d=i*i; d<=N; d+=2*i)
                ciur[d]=1;
        }
    for(; i<=N; i++)
        if(ciur[i]==0)
            prime[++cnt]=i;
    for(i=1; i<=n; i++)
    {
        in>>a>>b;
        desc(b);
        numar=a;
        for(j=1; j<=(1<<nr)-1; j++)
        {
            cnt=1;
            cate=0;
            for(k=0; k<=8; k++)
                if(j&(1<<k))
                {
                    cate++;
                    cnt*=cook[k+1];
                }
            if(cate%2)
                numar-=(a/cnt);
            else
                numar+=(a/cnt);
        }
        out<<numar<<'\n';
    }
    return 0;
}