#include <fstream>
#include <string.h>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long m, a, b, primes[80000], dp[100];
bool erst[1000000];

int erast()
{
    erst[2] = false;
    for (int i=2; i<=1000000; i++) {
        int p = 2;
        if (erst[i] == false) {
            while (1LL * i*p <= 1000000) {
                erst[i*p] = true;
                p++;
            }
        }
    }

    for (int i=2; i<=1000000; i++) {
        if (erst[i] == false)
            primes[++primes[0]] = i;
    }
}

void divprim(long long num)
{
    for (int i=1; i<=primes[0]; i++) {
        if (1ll * primes[i]*primes[i] > num)
            break;

        if (num % primes[i] == 0) {
            dp[++dp[0]] = primes[i];
            while (num % primes[i] == 0)
                num /= primes[i];
        }
    }

    if (num != 1)
        dp[++dp[0]] = num;
}

int main()
{
    erast();

    f>>m;
    for (int i=1; i<=m; i++) {
        f>>a>>b;

        memset(dp, 0, sizeof (dp));

        divprim(b);

        long long answ = 0;
        for (int i = 1; i < (1<<dp[0]); i++) {
            long long prod = 1, nbts = 0;

            for (int j = 0; j < dp[0]; j++) {
                if (i & (1<<j)) {
                    prod = prod * dp[j+1];
                    nbts++;
                }
            }

            if (nbts % 2 == 0)
                answ -= a / prod;
            else
                answ += a / prod;
        }

        g << a - answ <<"\n";
    }

    return 0;
}