#include <stdio.h>
char p[1000000/8/2+1];
long prim[100];
long long nr,t,a,c,b;
FILE *f,*g;
void ciur(long long A)
{
int i, j; nr = 0;
for (i = 1; ((i * i) << 1) + (i << 1) <= A; i += 1) {
if ((p[i >> 3] & (1 << (i & 7))) == 0) {
for (j = ((i * i
           ) << 1) + (i << 1); (j << 1) + 1 <= A; j += (i << 1) + 1) {
p[j >> 3] |= (1 << (j & 7));
}
}
}
if (b%2==0) prim[++nr]=2;
for (i = 1; 2 * i + 1 <= A; ++i)
if ((p[i >> 3] & (1 << (i & 7))) == 0)
                if (b%(2*i+1)==0)
                prim[++nr]=2*i+1;

}
void solve() {
    int i,j;
long long sol=a;
for (i=1;i<(1<<nr);i++) {
long long sm=0,prod=1;
for (j=0;j<nr;j++)
        if ((1<<j) & i) {
        prod=1LL*prod*prim[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,"%d",&t);
for (i=1;i<=t;i++) {
fscanf(f,"%lld%lld",&a,&b);
ciur(b);
solve();
}
fclose(g);
return 0;
}