#include <cstdio>
#include <cmath>
#define rad 1000010
#define N 100010

using namespace std;

int t,st[N];
long long p[N],c[N];
bool viz[rad];

void ciur()
{
t=1; p[1]=2;
for(int i=2; i<=rad; i+=2)viz[i]=1;
for(int i=3; i<=rad; i+=2)
    if(viz[i]==0)
            {
            p[++t]=i;
            for(int j=2*i; j<=rad; j+=i)
                viz[j]=1;
            }
}

int main()
{
int m;

ciur();
freopen("pinex.in","r",stdin); freopen("pinex.out","w",stdout);
scanf("%d\n",&m);
for(; m>=1; --m)
    {
    long long a,b;
    scanf("%lld %lld\n",&a,&b);
    int v=0; long long sol=0;
    for( int i=1; p[i]<=sqrt(b); ++i)
        if(b%p[i]==0){ c[++v]=p[i]; while(b%p[i]==0)b/=p[i]; }
    if(b!=0)c[++v]=b;
    int k=1; st[1]=-1; bool as;
    while(k>0)
        {
        if(st[k]<1){ ++st[k]; as=true; }
            else as=false;
        if(as)
            {
            if(k<v)st[++k]=-1;
                else {
                     long long pr=1; int nr=0;
                     for( int i=1; i<=k; ++i)
                        if(st[i]){ pr*=c[i]; ++nr; }
                     if(nr>0){
                            if(nr%2)sol+=(a/pr);
                                else sol-=(a/pr);
                           }
                     }
            }
        else --k;
        }
    printf("%lld\n",a-sol);
    }
fclose(stdin);
fclose(stdout);
return 0;
}