#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;
bool prime[1000010];
vector <int> _primes;

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

int main()
{ 
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);
	
	scanf("%d", &n);
	
	for (int i = 2; i <= 1000000; i++)
		if (!prime[i]) {
			
			for (int j = 2 * i; j <= 1000000; j += i) prime[j] = true;
		}
		
	for (int i = 2; i <= 1000000; i++)
		if (!prime[i]) _primes.push_back(i);
	
	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;
}