#include <fstream>
#define NMAx 1000100
using namespace std;
int nrPrime,nrDiv,prim[NMAx/2],Div[NMAx/2];
bool v[NMAx];
long long A,B,sol;

void ciur() {
	
	int i,j;
	
	prim[++nrPrime]=2;
	
	for(i=3;i<NMAx;i+=2)
		if(!v[i]) {
			prim[++nrPrime]=i;
			for(j=3*i;j<NMAx;j+=(i<<1))
				v[j]=1;
			}
	
}
void divizori(long long x) {
	
	int i;
	nrDiv=0;
	for(i=1;i<=nrPrime&&x>1;i++)
		if(x%prim[i]==0) {
			Div[++nrDiv]=prim[i];
			while(x%prim[i]==0)
				x/=prim[i];
			}
	
	if(x>1)
		Div[++nrDiv]=x;

}
void solve(long long A) {
	
	long long comb,p;
	int i,j,k;
	
	sol=A;
	
	for(i=1;i<(1<<nrDiv);i++) {
		
		comb=i;
		k=0;
		p=1;
		
		for(j=1;j<=nrDiv;j++)
			if(comb&(1<<(j-1))) {
				p*=Div[j];
				k++;
				}
		
		if(k%2==1)
			sol-=A/p;
		else
			sol+=A/p;
		
		}
	
}
int main() {
	
	int i,m;
	ifstream in("pinex.in");
	ofstream out("pinex.out");
	in>>m;
	
	ciur();
	
	for(i=0;i<m;i++) {
		in>>A>>B;
		divizori(B);
		solve(A);
		out<<sol<<'\n';
		}
	
	in.close();
	out.close();
	
	return 0;
}