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