#include <cstdio>

using namespace std;

const int lim=1000000;
int prim[lim];
long long v[20];
char vaz[lim+10];

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    int nrprim=0,n;
    for(int i=2;i<=lim;i++)
        if(!vaz[i])
        {
            prim[++nrprim]=i;
            if(1LL*i*i<=lim)
                for(int j=i*i;j<=lim;j+=i) vaz[j]=1;
        }
    for(scanf("%d",&n);n;n--)
    {
        int nr=0;
        long long a,b,sol=0;
        scanf("%lld%lld",&a,&b);
        for(int i=1;i<=nrprim && 1LL*prim[i]*prim[i]<=b;i++)
            if(b%prim[i]==0)
            {
                v[nr++]=prim[i];
                for(;b%prim[i]==0;b/=prim[i]);
            }
        if(b>1) v[nr++]=b;
        for(int i=1;i<(1<<nr);i++)
        {
            int s=0;
            long long p=1;
            for(int j=0;j<nr;j++)
                if(i&(1<<j)) {p*=v[j];s++;}
            if(s%2) sol+=a/p;
            else sol-=a/p;
        }
        printf("%lld\n",a-sol);
    }
    return 0;
}