write a go solution for Description:
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 Format:
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 Format:
Print T integers — one per test case. For each test case print the number of appropriate x-s.

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.. Output only the code with no comments, explanation, or additional text.