#include<fstream>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
const int PRE = 1000000;
int prim[80000];
int M;
long long A,B;
void ciur(){
	int i,j;
	char k[PRE+5];
	for(i=2;i<=PRE;i++) k[i]=1;
	for(i=2;i<=PRE;i++){
		if(k[i]==1){
			prim[++prim[0]]=i;
			for(j=i;j<PRE;j+=i){
				k[j]=0;
			}
		}
	}
}
int semn(int i){
	if(i%2==0) return -1;
	else return 1;
}
int v[20],p[20],l;
long long sumas,prod[20],n;
void update(int i){
	sumas+=semn(i)*(n/prod[i]);
}
void back(int i){
	for(p[i]=p[i-1]+1;p[i]<=l;p[i]++){
		prod[i]=prod[i-1]*v[p[i]];
		update(i);
		if(i<l) back(i+1);
	}
}
long long neprime(long long N){
	n=N;
	sumas=0;
	p[0]=0;
	prod[0]=1;
	back(1);
	return sumas;
}
long long procesare(long long N,long long D){
	int i=1; l=0;
	while(D>1 && i<=prim[0]){
		if(D%prim[i]==0){
			v[++l]=prim[i];
			while(D%prim[i]==0) D/=prim[i];
		}
		i++;
	}
	i=PRE+1;
	while(D>1){
		if(D%i==0){
			v[++l]=i;
			while(D%i==0) D/=i;
		}
		i++;
	}
	return N-neprime(N);
}
int main(){
	ciur();
	in>>M;
	for(int i=1;i<=M;i++){
		in>>A>>B;
		out<<procesare(A,B)<<'\n';
	}
	return 0;
}