给定三个正整数 $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