#include <cstdio>
using namespace std;

inline int cbits(int arg) {
    int ans = 0;
    while(arg) {
        if(arg&1)
            ++ans;
        arg>>=1;
    }
    return ans;
}

inline int pinex(int a, int b) {
    int f[25];
    int i, top, tmp, ans;

    ans = a;
    top = 0;
    i   = 1;

    while(i*i<=b) {
        ++i;
        if(b%i)
            continue;
        f[top++] = i;
        while(b%i==0)
            b/=i;
    }
    if(b>1)
        f[top++] = b;
    for(int i=1; i<(1<<top); ++i) {
        tmp = 1;
        for(int j=0; i>=(1<<j); ++j)
            if(i&(1<<j))
                tmp*=f[j];
        if(cbits(i)&1)
            ans-=a/tmp;
        else
            ans+=a/tmp;
    }
    return ans;
}

int main(void) {
    FILE *fi = fopen("pinex.in","r");
    FILE *fo = fopen("pinex.out","w");
    int m, a, b;
    fscanf(fi,"%d",&m);
    while(m--) {
        fscanf(fi,"%d%d",&a,&b);
        fprintf(fo,"%d\n",pinex(a, b));
    }

    fclose(fi);
    fclose(fo);
    return 0;
}