#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool c[1000020];
int f[800000], fact[800000];
ll solve(ll a, ll b){
	ll t=0, d=0;
	while(b > 1){
		++d;
		if(b%f[d]==0){
			fact[++t]=f[d];
			while(b>1 && b%f[d]==0) b/=f[d];
		}
		if(f[d]>sqrt(b) && b>1) {
			fact[++t]=b;
			b=1;
		}
	}
	ll rs=0, n= (1<<t);
	for(ll i=1; i<n;i++){
		ll prod=1, nr=0;
		for(int j=0;j<t;j++)
		if((1<<j) & i){
			prod=1LL*prod*fact[j+1];
			nr++;
		}
		if(nr%2) nr=1; else nr=-1;
		rs+= 1LL * (a/prod) * nr;
	}
	return a-rs;
}
int main(){
	for(int i=2;i<=1e6;i++)if(!c[i])
	{
		for(int j=i*2;j<=1e6;j+=i) c[j]=1;
		f[++f[0]]=i;
	}
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);
	int m;
	cin>>m;
	ll a;
	ll b;
	while(m--){
		cin>>a>>b;
		ll rs=solve(a, b);
		cout<<rs<<endl;
	}
	
	return 0;
}