#include <stdio.h>
#include <math.h>
char p[100000000];
long long prim[10000000];
long long fprim[100];

long long nr,t,a,c,b;
FILE *f,*g;
void ciur(long long A)
{
long long i2,i, j; nr = 0;

for (i = 3; i <= A; i += 2) {
    if (p[i >> 4] & (1 << ((i >> 1) & 7))) continue;

      for (j = i + (i2 = i + i); j <= A; j += i2)
            p[j >> 4] |= 1 << ((j >> 1) & 7);
}


for (i = 1; 2 * i + 1 <= A; ++i)
if ((p[i >> 3] & (1 << (i & 7))) == 0)
                prim[++nr]=2*i+1;

}
void solve() {
long long t=0,d=0;
while (b>1) {
    d++;
    if (b%prim[d] == 0) {
        fprim[++t]=prim[d];
        while (b % prim[d] == 0)
                b=b/prim[d];
        }

    if (prim[d]>sqrt(b) && b>1 ) {
        fprim[++t]=b;
        b=1;
        }
}

    int i,j;
long long sol=a;
for (i=1;i<(1<<t);i++) {
long long sm=0,prod=1;
for (j=0;j<t;j++)
        if ((1<<j) & i) {
        prod=1LL*prod*fprim[j+1];
        sm++;
        }
        if (sm%2==0) sm=1;
                else sm=-1;
        sol=sol+1LL*sm*a/prod;
}

fprintf(g,"%lld\n",sol);
}
int main () {
f=fopen("pinex.in","r");
g=fopen("pinex.out","w");
int i;
fscanf(f,"%lld",&t);
ciur(sqrtl(1000000000000));
for (i=1;i<=t;i++) {
fscanf(f,"%lld%lld",&a,&b);
solve();
}
fclose(g);
return 0;
}