# Summing the sum

Problem

Ishaan was playing with numbers. He knew how to calculate the sum of numbers. He defined a function for his use which calculates the twice sum of first N natural numbers as sum(N).

But being curious, he modified his function to calculate something more complex. He defined his function to be sumX(N,M,K).

Now this function calculates :

sum( K + sum( K + sum( K + ...sum(K + N)...))) , continuing for M terms (Refer example for explanation).

Given N, M and K, calculate the value of sumX(N,M,K).

Input

First line of input contains a single integer T denoting the number of test cases.

The only line of each test case contains 3 space-separated integers N, M and K.

Output

For each test case, print the required answer in a new line.

Constraints

1 <= T <= 200

1 <= N <= 1000

1 <= M <= 1000

1 <= K <= 1000

Input

3

1 2 3

2 2 2

3 3 2

Output

552

506

1120422

Explanation

Case 1 :

sum(3 + sum(3 + 1) ) = sum(3 + 20) = 552

Case 2 :

sum(2 + sum(2 + 2) ) = sum(2 + 20) = 506

Case 3 :

sum(2 + sum(2 + sum(2 + 3) ) ) = sum(2 + sum( 2 + 30 ) ) = sum(2 + 1056) = 1120422

Solution

The programming solution can get tricky, specially when using dynamic programming to solve. First we need the basic sum function that Ishaan had created

``````// to store all the summations calculated
private static int[] dp = new int;

private static int sum(int x) {
if (dp[x] != 0) {
return dp[x];
} else if (x == 0 || x == 1) {
return x;
} else {
// summation from x down to 0
dp[x] = x + sum(x - 1);
return dp[x];
}
}
``````

The array dp is used to store calculations that have already been made (to save time). The new sumX function calculates sum( K + sum( K + sum( K + ...sum(K + N)...))), for M terms. A bottom up procedure seems easiest, as the formula shows that the last calculation needed is sum(K+N) and it doesn't depend on another result. Therefore, doing this recursively becomes easier, as the base case is simple, and the sumX calculations can be reflected into programming easily

``````private static int sumX(int N, int M, int K) {
if (M == 1) {
// last calculation is just the summation of N + K
return 2 * sum(N + K);
} else {
// recursively calculate the summation of K + sumX(K + ...) M times
return 2 * sum(K + sumX(N, M - 1, K));
}
}
``````

And lastly, just call the sumX function with the data read in from the file that has similar data to

3

1 2 3

2 2 2

3 3 2

``````public static void main(String[] args) {
try {
// read in the data from file
Scanner scanner = new Scanner(new File("input.txt"));
int T = scanner.nextInt();
for (int x = 0; x < T; x++) {
int N = scanner.nextInt();
int M = scanner.nextInt();
int K = scanner.nextInt();
System.out.println(sumX(N, M, K));
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
``````

Credit to geeksforgeeks for the question.