#include <fstream>
//#include <iostream>
using namespace std;
long long unsigned int nr, s=0, v[5000];
int isprim(long long unsigned int k)
{
    if((k%2==0) && (k!=2))
        return 0;
        for(int i=3;i*i<=k;i=i+2)
            if(k%i==0)
                return 0;
    return 1;
}
int factprimi (long long unsigned int b)
{
    int i=2, c=0;
    while(b>1)
    {
        if(isprim(i))
        {
            if(b%i==0)
            {
                b=b/i;
                v[c]=i;
                c++;
                //cout<<n<<" ";
            }
            else i++;
        }
        else i++;
    }
    return c;
}
int feuler(long long int unsigned b, long long int unsigned n)
{
    long long unsigned int i, e=b;
    for(i=0;i<nr;i++)
    {
        e*=v[i]-1;
        e=e/v[i];
    }
    return e;
}
int cmmdc(long long unsigned int a, long long unsigned int b)
{
    long long unsigned int r;
    while(b)
        {
            r=a%b;
            a=b;
            b=r;
        }
    return a;
}
int main()
{
    long long unsigned int m, i,a, b, r, e, j, d;
    ifstream in ("pinex.in");
    ofstream out ("pinex.out");
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        nr=factprimi(b);
        //cout<<nr<<"\n";
        //for(j=0;j<nr;j++)
          //  cout<<v[j]<<" ";
        r=a/b;
        //cout<<"\n"<<r<<"\n";
        e=feuler(b, nr);
        //cout<<e<<"\n";
        e*=r;
        if(a!=b)
            for(j=(r*b)+1;j<=a;j++)
                {
                    d=cmmdc(j,b);
                    if(d==1)
                        e++;
                }
        out<<e<<"\n";
    }
    return 0;
    ///principiu lu peste
}