### 问题描述
在一个古老的城市中,有一座神秘的石柱。据说,这座石柱是由一位伟大的王者建造的,它蕴含着无尽的力量和智慧。但是,这座石柱的秘密被封印了,只有那些可以解开它秘密的人才能领悟它的智慧。
小蓝是一位勇敢的冒险家,她发现这座石柱隐藏了着两个神秘的数字 a 和 m。据她猜测,想要解开石柱的秘密,就要找到一个数字 x,使得 gcd,这样就能解开石柱的秘密了。
然而,小蓝追求的可不只是石柱的秘密,她更想知道的是在 [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