有一天ZKL遇到一道数学题。给定三个正整数a,b,m，问有多少个整数x满足0≤x<m并且gcd(a+b,m)=gcd(b-a+x,m)。但是这对于号称“数学天才”的ZKL来说过于简单了，所以现在她把这道问题抛给了你。
gcd(a,b)代表a和b的最大公约数。
第一行一个整数T代表有T组询问。(1 \le T \le 10)
接下来T行每行三个整数a,b,m(1 \le a \le b \le 10^{12} , 1 \le m \le 10^{12})。
T行，第i行代表第i组询问中，满足条件的x的数量