#include<fstream>
using namespace std;
long long x,numitor,nr1,card,a,b,i,j,k,l,prim[10000],n,nr;
bool ch[1000000];
long long p[10000];
int main(){
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	for (i=2;i<=100000/2;i++){
		if (ch[i]==false){
			for (j=2;j<=100000/i;j++)
				ch[i*j]=true;
		}
	}
	for (i=2;i<=100000;i++)
		if (ch[i]==false) {
			nr++;
			prim[nr]=i;
		}
	f>>n;
	for (l=1;l<=n;l++){
		f>>a>>b;
		nr=1;k=0;card=0;
		while (b!=1){
			if (b%prim[nr]==0) {
				k++;
				p[k]=prim[nr];
				b=b/p[k];
			}
			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;
		}
		g<<a-card<<"\n";
	};
	return 0;
}