#include <cstdio>
#include <vector>
using namespace std;

typedef long long i64;

#define pb push_back

int main()
{
	int M;
	i64 A,B;
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	for (scanf("%d",&M);M;M--)
	{
		scanf("%lld %lld",&A,&B);
		vector<i64> p;
		if (B % 2 == 0)
		{
			p.pb(2);
			while (B % 2 == 0) B/=2;
		}

		for (i64 d=3;d*d<=B;d+=2)
			if (B % d == 0)
			{
				p.pb(d);
				while (B % d == 0) B/=d;
			}

		if (B > 1) p.pb(B);
		i64 ans=A;

		for (int i=1;i<(1<<p.size());++i)
		{
			i64 d=1;
			int nr=0;
			for (int j=0;j<p.size();++j)
				if ((1<<j)&i)
				{
					++nr;
					d*=p[j];
				}
			if (nr&1) ans-=A/d;
			else ans+=A/d;
		}

		printf("%lld\n",ans);
	}

	return 0;
}