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