LCM and GCD

Problem Description

Given three positive integers $x, y, k$, find the number of ordered pairs $(a, b)$ satisfying

$$x \times \operatorname{lcm}(a,b) - y \times \gcd(a,b) = k$$

where $\operatorname{lcm}(a,b)$ is the least common multiple of $a$ and $b$, and $\gcd(a,b)$ is their greatest common divisor.

If $a \neq b$, then $(a,b)$ and $(b,a)$ are considered two different ordered pairs.

Input Format

The first line contains an integer $t$, the number of test cases ($1 \le t \le 10^3$).

Each of the next $t$ lines contains three integers $x, y, k$ as described above ($1 \le x, y, k \le 10^7$).

Output Format

Output $t$ lines, each containing one integer: the number of valid ordered pairs.

Sample Input

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

Sample Output

4
3
0
8