#include <fstream>
//#include <iostream>
using namespace std;
long long unsigned int nr, s=0, v[30], a, nrprime [78500];
bool prime [1000001];
void gen ()
{
    long long int n=0;
    int i, j;
    for (i = 2; i <= 1000000; ++i)
        prime[i] = 1;
    for (i = 2; i <= 1000000; ++i)
        if (prime[i])
        {
            nrprime[n]=i;
            n++;
            for (j = i+i; j <= 1000000; j += i)
                prime[j] = 0;
        }
}
long long unsigned int isprim(long long unsigned int k)
{
    long long unsigned int i;
    if((k%2==0) && (k!=2))
        return 0;
        for(i=3;i*i<=k;i=i+2)
            if(k%i==0)
                return 0;
    return 1;
}
void factprimi (long long unsigned int b)
{
    long long unsigned int i=2;
    nr=0;
    while(i<=78498)
    {
            if(b%i==0)
            {
                b=b/i;
                v[nr]=i;
                ++nr;
                while(b%i==0)
                    b=b/i;  //scapam de divizorii primi in plus
            }
            else i++;
    }
    if(b>1000000)
        if(isprim(b))
        {
            v[nr]=b;
            b=1;
            nr++;
        }
}
long long unsigned int pinex()
{
    long long int sol=0, i, j, p, n;
        for (i=1;i<(1<<nr);i++)
        {
            p=1;
            n=0;
            for(j=0;j<nr;j++)
                if((1<<j) & i)
                {
                p=1LL*p*v[j];
                n++;
                }
            if(n%2==1)
                sol=sol+a/p;
            else
                sol=sol-a/p;
        }
    return sol;
}
int main()
{
    long long unsigned int m, i, b, sol;
    ifstream in ("pinex.in");
    ofstream out ("pinex.out");
    gen ();
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        {
        factprimi(b);
        sol=pinex();
        out<<a-sol<<"\n";
        }

    }
    in.close();
    out.close();
    return 0;
}