Same GCDs

题意翻译

求 $$\sum_{x=0}^{m-1} [\ \gcd(a, m) = \gcd(a + x, m)\ ]$$ 多组测试数据, $T \leq 50,\ 1 \leq a < m \leq 10^{10}$

题目描述

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.

输入输出样例

输入样例 #1

3
4 9
5 10
42 9999999967

输出样例 #1

6
1
9999999966

说明

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