#include <fstream>
#include <cmath>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long i1,m,a,b,p,i,c,d,v[10000],j,nr,s,m1;
int main()
{
    f>>m1;
    for(i1=1; i1<=m1; i1++)
    {
        s=0;
        f>>a>>b;
        d=2;
        p=0;
        c=b;
        while(b>1&&d<=sqrt(c))
        {
            if(b%d==0) v[++p]=d;
            while(b%d==0) b/=d;
            d++;
        }
        if(b>1) v[++p]=b;
        for(i=1; i<(1<<p); i++)
        {
            nr=0;
            m=1;
            for(j=0; j<p; j++)
                if(i&(1<<j))
                {
                    nr++;
                    m*=v[j+1];
                }
            if(nr%2) s+=a/m;
            else s-=a/m;
        }
        g<<a-s<<'\n';


    }
    return 0;
}