F :: Find Pairs

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Matching pairs is a memory game that all of you may play at least once. There are (M*N)/2 distinct pictures that each of them is printed on the face of exactly two tiles. These tiles are initially laid face down and are distributed on an M by N board. It is clear that at least one of M and N should be even.

At each turn we choose one tile and flip it to see its picture, and then we select another tile and flip it in order to find the match for the previous flipped tile. If they are the same, both of them will remain face up, otherwise they return back face down. The goal is to match all of the pictures on the board.

I have a very young clever cousin that likes playing games. For the game described, she can only memorize K pictures along with their locations in her mind. When she flip a new tile, she see the picture of that tile and so she can compare it to her memorized pictures. Then, she can decide to forget the new tile, match the tile with the tiles in her memory or add its picture and location to her mind if she has still available memory.

As I told you, I know that she is very clever to finish the game as soon as possible. Tell me the maximum number of flips that she would have to finish the game.

Input

The first line of the input contains an integer T<=200 denoting the number of test-cases. Each test-case contains three space separated integers M, N, (1<=M,N<=1,000) and K (1<=K<=100) denoting the number of rows and columns of the board and the memory size of my cousin respectively.

Output

For each test-case, output on a single line the maximum number of flips that my cousin would have to finish the game.

Sample Input

2
2 3 5
2 2 1

Sample Output

10
8

Submit

Source: 13th Iran Nationwide Internet Contest - Shiraz