#include <cstdio>
#include <bitset>
using namespace std;
#define L 500000
#define NRP 78510
#define ll long long

bitset< L > e;
int prim[NRP];
ll d[65];
int lim;
ll rez,a,b;

inline void precalc() {
	for(int i=3; i*i<1000000; i+=2) {
        	if(e[(i>>1)]==1)
			continue;
		for(int j=i*i,i2=(i<<1); j<1000000; j+=i2)
			e[(j>>1)] = 1;
	}

        prim[0] = 1;
	prim[1] = 2;

	for(int i=3; i<1000000; i+=2) {
		if(e[(i>>1)]==0)
			prim[++prim[0]] = i;
	}
}

void back(ll x,int unde,int nrf) {
	if(unde==lim) {
		if((nrf&1)==1)
			rez -= (a/x);
		else
			rez += (a/x);
		return;
	}

	back(x,unde+1,nrf);
	if(a/x>=d[unde])
		back(x*d[unde],unde+1,nrf+1);
}

inline void rezolva() {
	scanf("%lld%lld",&a,&b);
        d[0] = 0;

	for(int i=1; i<=prim[0] && prim[i]*prim[i]<=b; ++i) {
		if(b%prim[i]==0) {
			d[++d[0]] = prim[i];

			while(b%d[d[0]]==0)
				b /= d[d[0]];
		}
	}

	if(b!=1)
		d[++d[0]] = b;
        lim = (int)d[0]+1;

	rez = 0;
	back(1,1,0);
	printf("%lld\n",rez);
}

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

	precalc();
	int T;
	scanf("%d",&T);

	for(; T>0; --T)
		rezolva();

	return 0;
}