CF1295D Same GCDs

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 $ .