#include <fstream>
#define ll long long
#define tix 1000000
using namespace std;
ll a,b,i,n,fact[1000005],j,sum,cb,ir,ci,fp,prod,p,k,t;
int x[100005];
int max(int a,int b)
{
    if (a<b) return b;
    return a;
}
int main()
{
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    f>>n;
    bool ok[1000005];
    for (i=2; i<=tix; i++)
        if (ok[i]==false)
        {
            fact[++fact[0]]=i;
            for (j=2*i; j<=tix; j+=i) ok[j]=true;
        }
    //ciur
    for (i=1; i<=n; i++)
    {
        f>>a>>b;
        cb=b;
        fp=0;
        sum=0;
        t=0;
        while (cb>1&&fact[max(fp,1)]*fact[max(1,fp)]<=cb)
        {
            fp++;
            if (cb%fact[fp]==0)
            {
                x[++t]=fact[fp];
                while (cb%fact[fp]==0) cb/=fact[fp];
            }
        }
        if (cb!=1) x[++t]=cb;
        for (ir=1; ir<(1<<t); ir++)
        {
            ci=ir;
            p=-1;
            prod=1;
            k=0;
            while (ci>0)
            {
                p++;
                if (ci%2==1) prod*=x[p+1],k++;
                ci/=2;
            }
            if (k%2==0) sum-=(a/prod);
            else sum+=(a/prod);
        }
        g<<a-sum<<'\n';
    }
    f.close();
    g.close();
    return 0;
}