# include <cstdio>
# include <algorithm>

using namespace std;

# define FIN "pinex.in"
# define FOUT "pinex.out"

const int MAX_N = 100000;
const int MAX_L = 20;
const int MAX_S = 1000001;

# define LL long long

int sol[MAX_L];
int nrp[MAX_N];
char prim[MAX_S];

long long A, B, j, total, rez, rad;
int M, i, cnt, csol, cur, prev, bnd, bit, nbit;

     inline int grey(int p) {
         return p ^ (p >> 1);
     }

     int main() {
         freopen(FIN, "r", stdin);
         freopen(FOUT, "w", stdout);
         
         memset(prim, 1, sizeof(prim));
         nrp[++cnt] = 2;
         for (i = 3; i < MAX_S; i += 2)
            if (prim[i]) {
                nrp[++cnt] = i;
                j = (LL) i * (LL) i;
                while (j < (LL) MAX_S) {
                    prim[j] = 0;
                    j += (LL) i;
                }
            }
            
         for (i = 0; i < MAX_L; ++i) prim[1 << i] = i + 1;
         
         scanf("%d", &M);
         for (; M; --M) {
             scanf("%lld %lld", &A, &B);
             
             for (i = 1, csol = 0; i <= cnt && 1LL * nrp[i] * nrp[i] <= B && B > 1; ++i)
                if (!(B % nrp[i])) {
                    sol[++csol] = nrp[i];
                    while (!(B % nrp[i])) B /= nrp[i];
                }
             if (B != 1) sol[++csol] = B;
             
             bnd = 1 << csol; prev = 0; total = 1; nbit = rez = 0;
             for (i = 1; i < bnd; ++i) {
                 cur = grey(i);
                 bit = cur ^ prev;
                 (bit & cur) ? total *= (LL) sol[prim[bit]], ++nbit : total /= (LL) sol[prim[bit]], --nbit;
                 (bit & 1) ? rez += A / total : rez -= A / total;
                 prev = cur;
             }
             
             printf("%lld\n", A - rez);
         }
         
         return 0;
     }