D. Same GCDs
math; number theory
You are given two integers \(a\) and \(m\). Calculate the number of integers \(x\) such that \(0 \le x < m\) and \(\gcd(a, m) = \gcd(a + x, m)\).Note: \(\gcd(a, b)\) is the greatest common divisor of \(a\) and \(b\).
The first line contains the single integer \(T\) (\(1 \le T \le 50\)) — the number of test cases.Next \(T\) lines contain test cases — one per line. Each line contains two integers \(a\) and \(m\) (\(1 \le a < m \le 10^{10}\)).
Print \(T\) integers — one per test case. For each test case print the number of appropriate \(x\)-s.
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\).