#include <bits/stdc++.h>
/// TONI BO$$ was here
/// #MLC

using namespace std;

char ciur[1000001];
int prime[100001],nr;

int main()
{
    int i,j,m,n,d,mask;
    long long a,b;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    for(i=4; i<=1000000; i+=2)
        ciur[i]=1;
    ciur[1]=0;
    for(i=3; i*i<=1000000; i+=2)
        if(ciur[i]==0)
            for(j=i*i; j<=1000000; j+=2)
                ciur[j]=1;
    for(i=2; i<=1000000; i++)
        if(!ciur[i])
            prime[++nr]=i;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%lld%lld",&a,&b);
        vector <long long> div;
        d=1;
        while(prime[d]*prime[d]<=b)
        {
            if(b%prime[d]==0)
            {
                div.push_back(prime[d]);
                while(b%prime[d]==0)
                    b/=prime[d];
            }
            d++;
        }
        if(b>1)
            div.push_back(b);
        n=div.size();
        long long rez=0;
        for(mask=1; mask<(1<<n); mask++)
        {
            long long prod=1;
            int ct=0;
            for(i=0; i<n; i++)
                if(((1<<i)&(mask)))
                    prod*=div[i],ct++;
            if(ct%2)
                rez+=(a/prod);
            else
                rez-=(a/prod);
        }
        printf("%lld\n",a-rez);
    }

    return 0;
}