有一天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的数量