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

int i,t,j,n;
long long  A,B,fact[500];
void eratostene();
vector<int> prime;
bitset<1000050> isprime;
int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	scanf("%d",&n);
	eratostene();
	vector<int>::iterator it;
	//for(it=prime.begin();it!=prime.end();it++)printf("%d ",*it);
	//printf("\n\n\n");
	for(;n--;)
	{
		scanf("%lld%lld",&A,&B);
		it=prime.begin();
		t=0;
		while(B>1)
		{
			if(it==prime.end())break;
			if(B%*it==0)
			{
				fact[++t]=*it;
				while(B%*it==0)B/=*it;
			}
			if(*it* *it>B&&B>1)
			{
				fact[++t]=B;
				B=1;
			}
			it++;
		}
		long long sol=A;
		int lim=1<<t;
		for(i=1;i<lim;i++)
		{
			long long prod=1;
			int nr=0;
			for(j=0;j<t;j++)
			{
				if((1<<j)&i)
				{
					prod=1LL*prod*fact[j+1];
					nr++;
				}
			}
			if(nr%2)nr=-1;
			else    nr=1;
			sol+=1LL*nr*A/prod;
		}
		printf("%lld\n",sol);
	}
}

void eratostene()
{
	prime.push_back(2);
	int i;
	for(i=3;i<=1000;i+=2)
	{
		if(isprime[i]==0)
		{
			prime.push_back(i);
			for(int j=i*i;j<=1000000;j+=i)
			{
				isprime[j]=1;
			}
		}
	}
	for(;i<=1000000;i+=2)
		if(isprime[i]==0)prime.push_back(i);
}