A and B

3.3

7 votes
Medium-Hard
Problem

Statement

Nik is bored of functions now and started looking for equations in Maths. Recently he saw an equation in two variables which was following:-
A * B = x + y * (gcd(A,B) + z * (lcm(A,B))

x,y and z were given to Nik and he had to find number of pairs (A,B) which will satisfy the given equation. gcd in the equation represents greatest common divisor and lcm stands for least common multiple of A and B. Nik was thinking of solution to the problem and Alex called him up. As he is now busy with Alex, you have to solve the question for him.

Input

  • The first line of the input contains T - number of test cases.
  • Each of the next T line contains 3 space separated integers x,y,z for that particular case.

Output

  • Output T lines where ith line contains the answer to the ith test case. If the answer is infinite output -1 instead.

Constraints

  • 1T105
  • 0x,y,z105
Sample Input
3
2 1 1
4 2 1
80 90 0
Sample Output
2
3
12
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For the first test case there are two pairs (2,4) and (4,2).

Contributers:
Editor Image

?