题目链接

题意

已知三个数 $c,d,x$ ，求有多少对正整数 $a,b$ 满足 $c\times lcm(a,b)- d\times gcd(a,b) = x$。

输入格式

第一行一个数 $t$ ，数据组数。$(1\le t\le 10^4)$

下面 $t$ 行，每行三个正整数 $c,d,x$。$(1\le c, d, x \le 10^7)$

输出格式

对于每组数据，输出一个数，表示答案。

样例

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

4
3
0
8