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