#include <fstream>
#include <math.h>
#include <bitset>
#define sqrtmaxB 1000000

using namespace std;

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

int primes[100001],factors[100001],p,f,M;
long long S,A,B;

bitset <sqrtmaxB+1> composite;

void Erathostenes (int n)
{
    primes[1]=2; p=1;
    int i;
    for (i=3; i*i<=n; i+=2)
    {
        if (composite[i]) continue;
        primes[++p]=i;
        for (int j=i*i; j<=n; j+=i) composite[j]=1;
    }
    for (;i<=n;i+=2)
    {
        if (!composite[i]) primes[++p]=i;
    }
}

long long subsets (int f)
{

    long long total=1<<f,S=0;
    for (int i=1; i<total; i++)
    {
        long long val=1; int nr=0;
        for (int j=0; j<f; j++)
            if ((i>>j)&1) {val=val*factors[j+1]; nr++;}
        if (nr&1) S+=A/val;
        else S-=A/val;
    }
    return S;
}

int main()
{
    Erathostenes (sqrtmaxB);
    fin>>M;
    for (int j=1; j<=M; j++)
    {
        fin>>A>>B;
        f=0;
        long long rad = sqrt (B);
        for (int i=1; i<=p && primes[i]<=rad; i++)
        {
            if (B%primes[i]==0)
            {
               while (B%primes[i]==0) B/=primes[i];
               factors[++f]=primes[i];
            }
        }
        if (B!=1) factors[++f]=B;
        S = subsets (f);
        fout<<A-S<<"\n";
    }
}