### 问题描述 小蓝设计了一个算法 $\gcd(a, m) = \gcd(a+x, m)$ 用来破解遗迹的信息。其中数字 $a$ 和 $m$ 是遗迹中的神秘数字。 为了检验算法的合理性，小蓝设计了一个数组 $[1, m)$ ，检验从中共有多少个 $x$ 能够解密成功。 你能帮助小蓝解决这个问题吗？ ### 输入格式 第一行包含一个整数 $T$（$1\leq T \leq 100$），表示测试用例的数量。 接下来 $T$ 行，每行包含两个整数 $a$ 和 $m$($1\leq a < m \leq 10^{5}$)。 ### 输出格式 对于每个测试用例，输出一个整数表示满足条件的 $x$ 的数量。 ### 样例输入 ``` 2 5 9 6 10 ``` ### 样例输出 ``` 6 4 ```