已知正整数 a,m ，求有多少整数 x 满足以下条件：
1.  0≤x<m ；
2.  gcd(a,m)=gcd(a+x,m) ；

其中 gcd(x,y) 表示求 x,y 的最大公约数。

第一行包含一个整数 T (1≤T≤50) ，表示数据组数。
每组数据一行，包含两个整数 a,m (1≤a<m≤10^10) 。

对于每组数据，输出一行包含一个整数，表示答案。

3
4 9
5 10
42 9999999967

6
1
9999999966