CF1499D.The Number of Pairs

You are given three positive (greater than zero) integers $c$ , $d$ and $x$ .

You have to find the number of pairs of positive integers $(a, b)$ such that equality $c \cdot lcm(a, b) - d \cdot gcd(a, b) = x$ holds. Where $lcm(a, b)$ is the least common multiple of $a$ and $b$ and $gcd(a, b)$ is the greatest common divisor of $a$ and $b$ .

The first line contains one integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.

Each test case consists of one line containing three integer $c$ , $d$ and $x$ ( $1 \le c, d, x \le 10^7$ ).

For each test case, print one integer — the number of pairs ( $a, b$ ) such that the above equality holds.

In the first example, the correct pairs are: ( $1, 4$ ), ( $4,1$ ), ( $3, 6$ ), ( $6, 3$ ).

In the second example, the correct pairs are: ( $1, 2$ ), ( $2, 1$ ), ( $3, 3$ ).