← 返回题目列表

Codeforces · 1499/D

D. 对数

中文机器翻译题面 查看原题

给您三个正(大于零)整数 $$$c$$$、$$$d$$$ 和 $$$x$$$。

您必须找到正整数对 $$$(a, b)$$$ 的数量,使得等式 $$$c \cdot lcm(a, b) - d \cdot gcd(a, b) = x$$$ 成立。其中 $$$lcm(a, b)$$$ 是 $$$a$$$ 和 $$$b$$$ 的最小公倍数,$$$gcd(a, b)$$$ 是 $$$a$$$ 和 $$$b$$$ 的最大公约数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由一行组成,其中包含三个整数 $$$c$$$、$$$d$$$ 和 $$$x$$$ ($$$1 \le c, d, x \le 10^7$$$)。

输出

对于每个测试用例,打印一个整数 — 满足上述等式的对 ($$$a, b$$$) 的数量。

示例

输入 #1

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

输出 #1

4
3
0
8

注意

在第一个示例中,正确的对是:($$$1, 4$$$)、($$$4,1$$$)、($$$3, 6$$$)、($$$6, 3$$$)。

在第二个示例中,正确的对是:($$$1, 2$$$)、($$$2, 1$$$)、($$$3, 3$$$)。