#include <fstream>
//#include <iostream>
using namespace std;
long unsigned int nr, s=0, v[5000];
bool prime [100005];
void gen ()
{
    int i, j;
    for (i = 2; i <= 100000; ++i)
        prime[i] = 1;
    for (i = 2; i <= 100000; ++i)
        if (prime[i])
        {
            //nr++;
            for (j = i+i; j <= 100000; j += i)
                prime[j] = 0;
        }
}
int isprim( 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 unsigned int b)
{
    int i=2, c=0, aux=b;
    while((b>1) && (i<=aux))
    {
        if(prime[i])
        {
            if(b%i==0)
            {
                b=b/i;
                v[c]=i;
                ++c;
                ++i;
                //cout<<n<<" ";
            }
            else i++;
        }
        else i++;
    }
    return c;
}
int feuler( long int unsigned b)
{
     long unsigned int i, e=b;
    for(i=0;i<nr;i++)
    {
        e*=v[i]-1;
        e=e/v[i];
        //cout<<e;
    }
    return e;
}
int cmmdc( long unsigned int a,  long unsigned int b)
{
     long unsigned int r;
    while(b)
        {
            r=a%b;
            a=b;
            b=r;
        }
    return a;
}
int main()
{
     long unsigned int m, i,a, b, r, e, j, d;
    ifstream in ("pinex.in");
    ofstream out ("pinex.out");
    gen ();
    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);
        //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
}