#include <stdio.h>
#include <vector>
#include <algorithm>
#define SZ(x) ((int)(x.size()))

using namespace std;

typedef long long int ll;

int n;
ll a, b;

vector <ll> get_prime_fact(ll x)
{
	vector <ll> answer;
	
	for (int i = 2; 1LL * i * i <= x; i++)
		if (x % i == 0) {
			
			answer.push_back(i);
			
			while (x % i == 0) x /= i; 
		}
		
	if (x > 1) answer.push_back(x);
	
	return answer;
}

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

	scanf("%d", &n);
	
	while (n--) {
		
		scanf("%lld %lld", &a, &b);
		
		vector <ll> primes = get_prime_fact(b);
		
		ll tot = 0;
		
		for (int i = 1; i < (1 << SZ(primes)); i++) {
			
			int nr = 0;
			ll cur = 1;
			
			for (int j = 0; j < SZ(primes); j++)
				if (((i >> j) & 1) == 1) {
					
					cur *= primes[j]; nr++;
				}
				
			if (nr % 2 == 0) nr = -1; else
				nr = 1;
				
			tot = tot + 1LL * nr * (a / cur); 
		}
		
		printf("%lld\n", a - tot);
	}	
	
	return 0;
}