#include <cstdio>

const int pmax = int(1e5);
const long long bmax = (long long)(1e12);
int primes[pmax];
char p[int(1e6)/16 + 2];

void sieve() {
	int n = int(1e6);
	for(int i = 1;((i*i)<<1) + (i<<1) <= n;i++) {
		if((p[i>>3] & (1<<(i & 7))) == 0) {
			for(int j = ((i*i)<<1) + (i<<1);(j<<1) + 1 <= n;j += (i<<1) + 1) {
				p[j>>3] |= 1<<(j & 7);
			}
		}
	}
	int num = 1;
	primes[0] = 2;
	for(int i = 1;(i<<1) + 1 <= n;i++) {
		if((p[i>>3] & (1<<(i & 7))) == 0) {
		//	printf("%d\n",2*i + 1);
			primes[num++] = (i<<1) + 1;
		}
	}
//	printf("%d\n",num);
}


int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
	sieve();
	int T;
	long long A, B;
	long long a[32];
	for(scanf("%d",&T);T;T--) {
		scanf("%lld %lld",&A,&B);
		int K = 0;
		long long b = B;
		for(int i = 0;1ll*primes[i]*primes[i] <= b;i++) {
			if(b%primes[i] == 0) {
				a[K++] = primes[i];
				do {
					b /= primes[i];
				} while(b%primes[i] == 0);
			}
		}
		if(b > 1) {
			a[K++] = b;
		}

		long long ans = 0;
		for(int i = 1;i < (1<<K);i++) {
			long long val = 1;
			int num = 0;
			for(int j = 0;j < K;j++) {
				if((i>>j) & 1) {
					val *= a[j];
					num++;
				}
			}
			ans += ((num & 1) ? 1 : -1)*A/val;
		}

		printf("%lld\n",A - ans);
	}
    return 0;
}