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.