- All Contests
- ProjectEuler+
- Project Euler #157: Solving the diophantine equation 1/a +1/b = p/10^n

# Project Euler #157: Solving the diophantine equation 1/a +1/b = p/10^n

# Project Euler #157: Solving the diophantine equation 1/a +1/b = p/10^n

_{This problem is a programming version of Problem 157 from projecteuler.net}

Consider the diophantine equation with , , positive integers and . This equation has solutions that are listed below:

Let's make generalized version of this equation: with positive integers , and primes , . How many solutions does this equation has for ?

Note, that if tuple occurs as a solution of the equation for multiple , it should be calculated multiple times and not once.

**Input Format**

Each test file starts with a number on a separate line which is the number of tests per file. lines follow, each containing , , and separated by single spaces.

**Constraints**

- are primes

**Output Format**

Output lines, each containing an answer to the corresponding test.

**Sample Input**

```
1
2 1 5 1
```

**Sample Output**

```
20
```