#include <bits/stdc++.h>

using namespace std;

long long i,n,a,b,ciur[100500],j,CIUR,D[300],d,rs;
bool e[1000005];

int main()
{
	ifstream cin("pinex.in");
	ofstream cout("pinex.out");
	for (i=2; i<=1000000; i++)
		if (!e[i])
			for (j=2; j<=1000000/i; j++)
				e[i*j]=true;
	for (i=2; i<=1000000; i++)
		if (!e[i]) ciur[++CIUR]=i;
	cin>>n;
	for (i=1; i<=n; i++)
	{
		cin>>a>>b;
		d=rs=0;
		for (j=1; ciur[j]<=sqrt(b); j++)
		{
			if (b%ciur[j]==0) 
			{
				D[d++]=ciur[j];
				while (b%ciur[j]==0) b/=ciur[j];
			}
		}
		if(b>1) D[d++] = b;
		for (long long j=1; j<(1<<d); j++)
		{
			long long k=0,pr=1,semn=-1;
			for (long long z=0; z<d; z++) if ((1<<z)&j) pr*=D[z],k++;
			if (k%2) semn=1;
			rs+=(a/pr)*(semn);
		}
		cout<<a-rs;
	}
}