给您三个正(大于零)整数 $$$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$$$)。