#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;

#define LMAX 1000001
int p[LMAX],d[LMAX],fact[LMAX];

inline void ciur()
{
	int i,j;
	for(i=2;i<=LMAX-1;i++)
		if(p[i]==0) {
			for(j=i+i;j<=LMAX-1;j=j+i)
				p[j]=1;
			fact[++fact[0]]=i;
		}
}

long long solve(long long a, long long b)
{
	long long sol,i,j,stop,k,prod;
	int nr;
	if(b==1)
		return a;
	i=2;
	k=0;
	while(b>1 && i<=fact[0]) {
		if(b%fact[i]==0) {
			d[++k]=fact[i];
			while(b%fact[i]==0)
				b=b/fact[i];
		}
		i++;
	}
	if(b>1)
		d[++k]=b;
	sol=0;
	for(i=1;i<=(1LL<<k)-1;i++) {
		nr=0;
		prod=1;
		for(j=0;j<=k-1;j++)
			if(i&(1<<j)) {
				nr++;
				prod=1LL*prod*d[j+1];
			}
		if(nr%2==0)
			nr=-1;
		else nr=1;
		sol=0LL+sol+1LL*nr*a/prod;
	}
	return 0LL+a-sol;
}

int main ()
{
	int m,i;
	long long a,b;
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	f>>m;
	ciur();
	for(i=1;i<=m;i++) {
		f>>a>>b;
		g<<solve(a,b)<<'\n';
	}
	f.close();
	g.close();
	return 0;
}