### 问题描述 在一个古老的城市中，有一座神秘的石柱。据说，这座石柱是由一位伟大的王者建造的，它蕴含着无尽的力量和智慧。但是，这座石柱的秘密被封印了，只有那些可以解开它秘密的人才能领悟它的智慧。 小蓝是一位勇敢的冒险家，她发现这座石柱隐藏了着两个神秘的数字 $a$ 和 $m$。据她猜测，想要解开石柱的秘密，就要找到一个数字 $x$，使得 $\gcd(a, m) = \gcd(a+x, m)$，这样就能解开石柱的秘密了。 然而，小蓝追求的可不只是石柱的秘密，她更想知道的是在 $[1, m)$ 中总共有多少个 $x$ 能够解密。请你编写一个程序，计算出满足条件的 $x$ 的数量。 ### 输入格式 第一行包含一个整数 $T$（$1\leq T \leq 20$），表示测试用例的数量。 接下来 $T$ 行，每行包含两个整数 $a$ 和 $m$($1\leq a < m \leq 10^{9}$)，表示石柱上刻着的数字和一个神秘的数字。 ### 输出格式 对于每个测试用例，输出一个整数表示满足条件的 $x$ 的数量。 ### 样例输入 ``` 2 5 9 6 10 ``` ### 样例输出 ``` 6 4 ```