#include <cstdio>
#include <math.h>

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
	int T, A, B;
	int a[32], K = 0;
	for(scanf("%d",&T);T;T--) {
		scanf("%d %d",&A,&B);
		int d = 2;
		int b = B;
		K = 0;
		if(b%d == 0) {
			a[K++] = d;
			do {
				b /= d;
			}
			while(b%d == 0);
		}

		for(d = d + 1;d*d <= b;d += 2) {
			if(b%d == 0) {
				a[K++] = d;
				do {
					b /= d;
				} while(b%d == 0);
			}
		}
		if(b > 1) {
			a[K++] = b;
		}
		int ans = 0;
		for(int i = 1;i < (1<<K);i++) {
			int val = 1;
			int num = 0;
			for(int j = 0;j < K;j++) {
				if((i>>j) & 1) {
					val *= a[j];
					num++;
				}
			}
			//printf("%d ",val);
			ans += ((num & 1) ? 1 : -1)*A/val;
		}

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