405360: GYM101915 E Minesweeper

Have you ever played Minesweeper? It’s a cute little game that originates from the 1960s, and has been written for many computing platforms in use today.

The game consists of a two dimensional grid, and there are two types of cells in it.

A mined cell, and an empty cell, which contains a single digit that indicates how many adjacent cells contain mines. Eech cell has at most 8 adjacent cells.

In this version of the game, you are going to build a level with the following rules:

• Every mined cell has to be a neighbor of at least one empty cell.

• Every empty cell can have at most M adjacent mines.

For instance, the following is 4 * 5 valid grid with 12 mines (which are represented by an '*' character) and the maximum number for the empty cells is M = 3 :

We are interested in the maximum number of mines that a grid with those properties can contain, can you find the answer for us?

The first line contains a single integer T denoting the number of test cases.

Each test case consists of one line which contains three space separated integers:

The number of the rows in the grid r. (2 ≤ r ≤ 6).

The number of the columns in the grid c. (2 ≤ c ≤ 6).

The maximum number that any empty cell can contain. (1 ≤ M ≤ 8).

For each test print one line containing one integer, the maximum number of mines that a grid can contain.

2
4 5 3
3 3 4

12
6

The grid in the statement is a valid grid for the first sample.