#include <fstream>
#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;
    }
}

void subsets (int k, int val, int nr)
{
    if (nr%2) S = S + (A/val);
        else S = S - (A/val);

    for (int i=k; i<=f; i++)
    {
        subsets (i+1,val*factors[i],nr+1);
    }
}

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