#include <stdio.h>

#define MAXNR 1000000
#define MAXPRIME 78500
#define MAXFACT 11

int prime[MAXPRIME + 1], fp[MAXFACT + 1];
char ciur[MAXNR + 1];

int descompunere(long long n) {
    int k, i;

    k = 0;
    i = 1;
    while (n > 1) {
        if (n % prime[i] == 0) {
            fp[++k] = prime[i];
            while (n % prime[i] == 0) {
                n /= prime[i];
            }
        }
        i++;

        if (prime[i] * prime[i] > n && n > 1) {
            fp[++k] = n;
            n = 1;
        }
    }

    return k;
}

int main() {
    FILE *fin, *fout;
    int n, k, prod, nr, mask, d, i, j;
    long long a, b, sol;

    ciur[0] = ciur[1] = 1;
    for (d = 2; d * d <= MAXNR; d++) {
        if (ciur[d] == 0) {
            for (i = d * d; i <= MAXNR; i += d) {
                ciur[i] = 1;
            }
        }
    }

    d = 0;
    for (i = 2; i <= MAXNR; i++) {
        if (ciur[i] == 0) {
            prime[++d] = i;
        }
    }

    fin = fopen("pinex.in", "r");
    fscanf(fin, "%d", &n);
    fout = fopen("pinex.out", "w");
    for (i = 1; i <= n; i++) {
        fscanf(fin, "%lld%lld", &a, &b);

        k = descompunere(b);
        sol = 0;

        for (mask = 1; mask < (1 << (k + 1)); mask++) {
            prod = 1;
            nr = 0;

            for (j = 1; (1 << j) <= mask; j++) {
                if ((1 << j) & mask) {
                    nr++;
                    prod *= fp[j];
                }
            }

            sol += (a / prod) * (2 * (nr % 2) - 1);
        }
        fprintf(fout, "%lld\n", (a - sol) / 2);
    }
    fclose(fin);
    fclose(fout);

    return 0;
}