#include <bits/stdc++.h>
#define maxi 1000005
using namespace std;
fstream f1("pinex.in", ios::in);
fstream f2("pinex.out", ios::out);
int t, ciur[maxi+5]; ///ciur[i]=0 daca i prim
long long int a, b, nrel, f[maxi], prime[maxi+5], nrprime;
void eratostene()
{
    long int i, j;
    ciur[0]=ciur[1];
    for(i=2; i<maxi; i++)
        if(!ciur[i])
       {
        nrprime++;
        prime[nrprime]=i;
        for(j=i*2; j<maxi; j+=i)
            ciur[j]=1;
       }
}
void fact_primi()
{
    long long int i=1, limita=sqrt(b), ok;
    nrel=0;
    while((b!=1)&&(i<=nrprime))
    {
        ok=0;
        if(prime[i]> limita) break;
        while(b% prime[i]==0)
        {
            b/=prime[i];
            ok=1;
        }
        if(ok)
        {
            nrel++;
            f[nrel]=prime[i];
        }
        i++;
    }
    if(b!=1)
    {
        nrel++;
        f[nrel]=b;
    }
}
void solutie()
{
    long long int i, rez=0, nrsub=(1<<nrel)-1, p, nr, bit; ///nrsub= nr submultimi formata cu fact primi ai lui b - mult vida
    for(i=1; i<=nrsub; i++)
    {
        p=1; nr=0;
        ///i= config in binar a multimii
        for(bit=0; (1<<bit)<=i; bit++)
            if((1<<bit)&i)
        {
            nr++;
            p*=f[bit+1];
        }
        if(nr%2==1) rez+=a/p;
        else    rez-=a/p;
    }
    f2<<a-rez<<"\n";
}
int main()
{
    int i;
    f1>>t;
    eratostene();
    for(i=1; i<=t; i++)
    {
        f1>>a>>b;
        fact_primi();///pt b
        solutie();
    }
    return 0;
}