HZNUOJ

A Very Easy Math Problem

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:84     AC:33     Score:100.00

Description

有一天ZKL遇到一道数学题。给定三个正整数a,b,m,问有多少个整数x满足0≤x<m并且gcd(a+b,m)=gcd(b-a+x,m)但是这对于号称“数学天才”的ZKL来说过于简单了,所以现在她把这道问题抛给了你。

gcd(a,b)代表a和b的最大公约数。

Input

第一行一个整数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}$)。

Output

T行,第i行代表第i组询问中,满足条件的x的数量

Samples

input
3 1 2 3 2 2 9 12 123 1234
output
1 6 616

Author

QIU, Longfeng