Logo Daimayuan Online Judge

Home

时间限制:3 s 空间限制:1024 MB

#953. LCM与GCD

附加文件 统计

给定三个正整数 $x,y,k$ , 求满足 $x \times lcm(a,b) - y \times gcd(a,b) = k$ 的数对 $(a,b)$ 的数量 ,其中 $lcm(a,b)$ 是 $a,b$ 的最小公倍数 , $gcd(a,b)$ 是 $a,b$ 的最大公约数。

若 $a \neq b$ 那么 $(a,b)$ 与 $(b,a)$ 是两个不同的数对。

输入格式

第一行一个整数 $t$ , 表示数据组数。$(1 \leq t \leq 10^3)$

接下来 $t$ 行,每行输入三个整数 $ x,y,k $ , 含义如题面所示。 $ ( 1 \leq x,y,k \leq 10^7 ) $。

输出格式

输出 $t$ 行,每行一个整数,表示满足要求二元对的数量。

样例输入

4
1 1 3
4 2 6
3 3 7
2 7 25

样例输出

4
3
0
8