13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T5c3,

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$$$.

Input

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$$$).

Output

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

Note

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

In the se

The Number of Pairs

Examples