#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
int gcd(int a,int b) {return b?gcd(b,a%b):a;}
signed main()
{
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		int a,m;
		cin>>a>>m;
		m/=gcd(a,m);
		int x=m;
		for(int i=2;i*i<=m;i++)
		{
			if(m%i==0)
			{
				while(m%i==0) m/=i;
				x-=x/i;
			}
		}
		if(m>1) x-=x/m;
		cout<<x<<endl;
	}
	return 0;
}

answer.code: In function 'int main()':
answer.code:8:10: error: 'nullptr' was not declared in this scope
  cin.tie(nullptr) -> sync_with_stdio(false);\x0d
          ^