D. Same GCDs (Educational Codeforces Round 81 (Rated for Div. 2))

D. Same GCDs

You are given two integers a and m. Calculate the number of integers x such that 0≤x<m and gcd(a,m)=gcd(a+x,m)

Note: gcd(a,b) is the greatest common divisor of a and b.

Input

The first line contains the single integer T (1≤T≤50) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains two integers a and m (1≤a<m≤10^10).

Output

Print T integers — one per test case. For each test case print the number of appropriate x-s.

Example

input

Copy

3
4 9
5 10
42 9999999967

output

Copy

6
1
9999999966

Note

In the first test case appropriate x-s are [0,1,3,4,6,7]

In the second test case the only appropriate x is 0

题意：找有多少个x满足gcd(a,m)=gcd(a+x,m)，x小于m

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//直接求解欧拉函数    
ll euler(ll n) { //返回euler(n)     
	ll res = n, a = n;
	for (ll i = 2; i*i <= a; i++) {
		if (a%i == 0) {
			res = res / i * (i - 1);//先进行除法是为了防止中间数据的溢出     
			while (a%i == 0) a /= i;
		}
	}
	if (a > 1) res = res / a * (a - 1);
	return res;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		ll a, m;
		cin >> a >> m;
		ll g = __gcd(a, m);
		m /= g;
		cout << euler(m) << endl;
	}
}