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

ll D[30];
bool E[MAXN];
vector <int> Dt;

int main(){
	ifstream cin("pinex.in");
	ofstream cout("pinex.out");
	int t;
	cin>>t;
	for(int i=2;i<MAXN;i++){
		if(!E[i]){
			Dt.push_back(i);
			if(i<=sqrt(MAXN)){
				ll j=i*i;
				while(j<MAXN){
					E[j]=1;
					j+=i;
				}
			}
		}
	}
	while(t--){
		ll a,b,n=0;
		cin>>a>>b;
		int i=0;
		while(b>1 && i<Dt.size()){
			if(b%Dt[i]==0){
				D[n++]=Dt[i];
				while(b%Dt[i]==0)b/=Dt[i];
			}
			if(Dt[i]>sqrt(b) && b>1){
					D[n++]=b;
					b=1;
			}
			i++;
		}
		ll s=a,l=(1<<n);
		for(int i=1;i<l;i++){
			ll c=0, prod=1;
			for(int j=0;j<n;j++){
				if((1<<j)&i){
					prod*=D[j];
					c++;
				}
			}
			if(c%2)prod=-prod;
			s+=a/prod;
		}
		cout<<s<<'\n';	
	}
	return 0;
}