x*y = a + b*lcm(x,y) + c*gcd(x,y)

It's easy: you are to write a program which for given a, b and c finds the number of pairs of positive integers (x, y) satisfying this equation.

Here * stands for multiplication, gcd(x,y) stands for the greatest common divisor of x and y, while lcm(x,y) stands for the least common multiple of x and y.

Input

The first line of the input file contains one integer T -- the number of test cases (no more than 10). Each of the next T lines contains exactly three space-separated integers a, b and c (0 ≤ a, b, c ≤ 106).

Output

For each test case output one line containing the sought number of solutions to the equation. If there is an infinite number of solutions, output -1 instead.

Example

Input:

3

2 1 1

160 0 90

300 7 5

Output:

2

8

4

Explanation:

In the first test case, the only pairs are (2,4) and (4,2).

given: xy = a + b*lcm + c*gcd

- ashu February 19, 2012elementry maths: xy = lcm*gcd, on substitution, we get: lcm*gcd = a + b*lcm + c*gcd

on rearranging, we get (gcd - b)(lcm - c) = a + bc.

This is a program of finding all pairs of numbers p,q such that pq = k.

=> lcm - c = x1, gcd - b = x2

=> lcm = x1 + c, gcd = x2 + b

Now xy = lcm*gcd => x*y = (x1+c)(x2+b) Which is again a case of pq = k. Call the same function again and count the number of values found, which is our output.