Joyful

Sakura has a very magical tool to paint walls. One day, kAc asked Sakura to paint a wall that looks like an $M \times N$ matrix. The wall has $M \times N$ squares in all. In the whole problem we denotes $(x, y)$ to be the square at the $x$-th row, $y$-th column. Once Sakura has determined two squares $(x_1, y_1)$ and $(x_2, y_2)$, she can use the magical tool to paint all the squares in the sub-matrix which has the given two squares as corners.

However, Sakura is a very naughty girl, so she just randomly uses the tool for $K$ times. More specifically, each time for Sakura to use that tool, she just randomly picks two squares from all the $M \times N$ squares, with equal probability. Now, kAc wants to know the expected number of squares that will be painted eventually.

The first line contains an integer $T$($T \le 100$), denoting the number of test cases.

For each test case, there is only one line, with three integers $M, N$ and $K$.
It is guaranteed that $1 \le M, N \le 500$, $1 \le K \le 20$.

For each test case, output ''Case #t:'' to represent the $t$-th case, and then output the expected number of squares that will be painted. Round to integers.

2
3 3 1
4 4 2

Case #1: 4
Case #2: 8

The precise answer in the first test case is about 3.56790123.

The 2015 ACM-ICPC China Shanghai Metropolitan Programming Contest