#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll A,B;
int D[200],P[100010],m,p;
bool ciur[1000010];

int main(){
	ifstream cin ("pinex.in");
	ofstream cout ("pinex.out");
	cin>>m;
	ciur[1]=true;
	for (int i=2; i<=1000000; i++){
		if (!ciur[i]){
			P[++p]=i;
			for (int j=i+i; j<=1000000; j+=i) ciur[j]=true;
		}
	}
	for (int w=1; w<=m; w++){
		cin>>A>>B;
		int d=0;
		for (int i=1; P[i]<=sqrt(B); i++){
			if (B%P[i]==0){
				D[d++]=P[i];
				while (B%P[i]==0) B/=P[i];
			}
		}
		if (B>1) D[d++]=B;
		int rs=0;
		for (int i=1; i<(1<<d); i++){
			int k=0,prod=1;
			for (int j=0; j<d; j++){
				if ((1<<j)&i) prod*=D[j],k++;
			}
			rs+=A/prod*(k%2?1:-1);
		}
		cout<<A-rs<<"\n";
	}
	return 0;
}