#include <fstream>
#include <cmath>
using namespace std;

int m, fp[10000], i, j, k;
bool neprim[1000001];
unsigned long long A, B, db[30], prod, sol, nr;

ifstream f("pinex.in");
ofstream g("pinex.out");

int main()
{   f>>m;
    for (i=2; i<=1000000; ++i)
        if (!neprim[i])
        {   fp[++fp[0]]=i;
            for (j=2; j*i<=1000000; ++j)
                neprim[j*i]=1;
        }
    for (; m; --m)
    {   f>>A>>B;
        k=0;
        for (i=1, k=0; B!=1; ++i)
        {   if (B%fp[i]==0)
            {   db[++k]=fp[i];
                while (B%fp[i]==0)
                    B/=fp[i];
            }
            if (fp[i]>sqrt(B) && B!=1)
            {   db[++k]=B;
                B=1;
            }
        }
        sol=0;
        for (unsigned long long i=1; i<(1<<k); ++i)
        {   prod=1;
            for (j=0, nr=0; j<k; ++j)
                if ((1<<j)&i)
                {   prod*=db[j+1];
                    ++nr;
                }
            if (nr%2)
                nr=1;
            else
                nr=-1;
            sol+=A/prod*nr;
        }
        g<<A-sol<<'\n';
    }
    return 0;
}