#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#define MAXQ 1100100

using namespace std;

int m;
vector<int> prim;
vector<int> divs;
bitset<MAXQ> viz;

void prepare()
{
    /// sieve
    prim.push_back(2);
    for (int i = 3; i < MAXQ-10; i+=2) {
        if (!viz[i]) prim.push_back(i);
        for (int j = 3*i; j < MAXQ-10; j += (i<<1))
			viz[j] = 1;
    }
    /// debug
//    for (int i = 0; i < 20; i++)
//		printf("%d ", prim[i]);
}

long long solve(long long a, long long b)
{
	divs.clear();
	for (int i = 0; prim[i] <= b; i++)
		if (b%prim[i] == 0) {
			divs.push_back(prim[i]);
			while (b%prim[i] == 0)
				b /= prim[i];
		}
	if (b > 1) divs.push_back(b);

	int n = divs.size();
	long long card = 0; /// cardinal of reunion of multiples of divs[0...size]
	for (int i = 1; i < (1<<n); i++) {
        long long fact = -1;
        for (int j = 0; i >> j; j++)
            if ((i>>j) & 1)
                fact *= -divs[j];
		card += a/fact;
	}
	return a - card;
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

	long long a, b;
	prepare();
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%lld %lld", &a, &b);
        printf("%lld\n", solve(a, b));
    }
    return 0;
}