#include<stdio.h> 
#include<math.h> 
# include <algorithm> 
using namespace std; 
long long x,numitor,nr1,card,a,i,j,k,l,prim[100100],n,nr; 
bool ch[1000100]; 
long long p[100100]; 
long long b,crer; 
void ciur() { 
	fill(ch + 2,ch +500000, 1); 
	nr=0; 
	for (int i = 2;i<500000; i++) 
		if (ch[i]) { 
			for (int j = 2 * i; j < 500000; j += i) 
				ch[j] = false; 
			prim[++nr] = i; 
		} 
} 
int main(){    
	freopen("pinex.in","r",stdin); 
	freopen("pinex.out","w",stdout); 
	prim[1]=2; nr=1;  
	ciur(); 
	scanf("%lld\n",&n); 
	for (l=1;l<=n;l++){ 
		scanf("%lld %lld\n",&a,&b); 
		nr=1;k=0;card=0;  
		long long crer=b; 
		while (b>1){ 
			if (b%prim[nr]==0) { 
				k++; 
				p[k]=prim[nr];               
				while (b%prim[nr]==0) 
					b=b/p[k];
			} 
			if(b>1 && prim[nr]>sqrt(crer))  {                   
				p[++k]=b; 
				b=1; 
			} 
			nr++; 
		} 
		for (i=1;i<1<<k;i++){ 
			x=i; 
			numitor=1;
			nr1=0; 
			for (j=1;j<=k;j++){ 
				if (x%2==1){
					numitor=numitor*p[j]; 
					nr1++; 
				} 
				x=x/2; 
			} 
			if (nr1%2==1) card=card+a/numitor; 
			else card=card-a/numitor; 
		} 
		printf("%lld\n",a-card); 
	}; 
	return 0; 
}