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:
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 :
* * * * 2
* * * * 2
3 * * 3 1
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.
The grid in the statement is a valid grid for the first sample.
## Input
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).
## Output
For each test print one line containing one integer, the maximum number of mines that a grid can contain.
[samples]
## Note
The grid in the statement is a valid grid for the first sample.
**Definitions**
Let $ A \in [0, 359] \cap \mathbb{Z} $ be the rotation angle (in degrees).
Let $ W, H \in \mathbb{Z}^+ $, $ W, H \leq 10^9 $, be the width and height of the window.
Let $ N \in \mathbb{Z} $, $ 3 \leq N \leq 10^5 $, be the number of vertices.
Let $ P = \{(x_i, y_i) \in \mathbb{Z}^2 \mid 0 \leq x_i, y_i \leq 10^9, i \in \{1, \dots, N\} \} $ be the input polygon.
**Transformations**
1. **Rotation**: Rotate each point $ (x_i, y_i) $ counterclockwise by angle $ A $ degrees:
$$
(x_i', y_i') = \left( x_i \cos \theta - y_i \sin \theta,\ x_i \sin \theta + y_i \cos \theta \right), \quad \theta = \frac{A \pi}{180}
$$
2. **Scaling and Translation**:
Let $ x_{\min} = \min_i x_i' $, $ x_{\max} = \max_i x_i' $,
$ y_{\min} = \min_i y_i' $, $ y_{\max} = \max_i y_i' $.
Scale and translate to fit the window:
$$
\hat{x}_i = W \cdot \frac{x_i' - x_{\min}}{x_{\max} - x_{\min}}, \quad
\hat{y}_i = H \cdot \frac{y_i' - y_{\min}}{y_{\max} - y_{\min}}
$$
**Objective**
Output the transformed points $ (\hat{x}_i, \hat{y}_i) $ for $ i = 1, \dots, N $, with absolute or relative error $ \leq 10^{-6} $.