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

typedef long long i64;
const int SQRT_B=1000005;

#define pb push_back

bool prim[SQRT_B];
vector<int> Primes;

void eratostene()
{
	int i,j;
	for (i=0;i<SQRT_B;++i) prim[i]=true;
	prim[0]=prim[1]=false;
	for (i=2;i<SQRT_B;++i)
		if (prim[i])
			for (j=i*2;j<SQRT_B;j+=i) prim[j]=false;
	
	for (i=2;i<SQRT_B;++i) 
		if (prim[i]) Primes.pb(i);
}

int main()
{
	int M;
	i64 A,B;
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	eratostene();
	for (scanf("%d",&M);M;M--)
	{
		scanf("%lld %lld",&A,&B);
		vector<i64> p;
		
		for (size_t i=0;i<Primes.size();++i)
		{
			if ((i64)Primes[i]*Primes[i] > B) break;
			if (B % Primes[i] == 0)
			{
				p.pb(Primes[i]);
				while (B % Primes[i] == 0) B/=Primes[i];
			}
		}
		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 (size_t 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;
}