// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define int long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
const int mod=998244353,maxn=500005;
int getphi(int x){
	int ans=1;
	for(int i=2;i*i<=x;++i)if(x%i==0){
		ans*=(i-1),x/=i;
		for(;x%i==0;x/=i)ans*=i;
	}
	if(x>1)ans*=(x-1);
	return ans;
}
void solve(){
	int x,y; cin>>x>>y;
	cout<<getphi(y/__gcd(x,y))<<endl;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1; cin>>zsy;
	F(____,1,zsy)solve();
}