#include <stdio.h>
#include <string.h>
#define MAXRAD 1000010

int P[50000];
bool prim[MAXRAD];
long long A, B, sum;
int T, D[20];


inline void factori()
{
	memset(prim, true, sizeof(prim));
	P[++P[0]] = 2;
	for (int i=3; i<MAXRAD; i+=2)
		if (prim[i]){
			P[++P[0]] = i;
			for (int j=3*i; j<MAXRAD; j+=(i<<1))
				prim[j] = false;
		}
}

void back(int lv, long long prod, int nr)
{
	if (lv == D[0]+1){
		if (nr&1 == 1)
			sum -= (A / prod);
		else
			sum += (A / prod);
	}
	else{
		back(lv+1, prod*D[lv], nr+1);
		back(lv+1, prod, nr);
	}
}

inline void solve()
{
	scanf("%lld %lld",&A, &B);
	D[0] = 0; sum = 0;
	for (int i=1; i<P[0] && B/P[i] >= P[i]; i++)
		if (B%P[i] == 0){
			D[++D[0]] = P[i];
			while (B%P[i] == 0)
				B/=P[i];
		}
	if (B!=1) D[++D[0]] = (int)B;
	back(1,1,0);
	printf("%lld\n",sum);
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	factori();
	for (scanf("%d",&T); T; T--)
		solve();
	return 0;
}