Sweeper's Dillemma

Minesweeper is a popular single-player puzzle video game from the 60's. It still enjoys the privilege to get shipped with popular operating systems. Many people, unaware of the rules of this game, makes random clicks and end up losing the game. It is true that in some cases, this game requires a bit of luck. But mostly, this is a puzzle. The implementation of this game requires Depth-First Search and lets you brag about your algorithmic skills to your C instructor.

Talking about luck, the very first move of this game is a random click. An unlucky player could end up losing the game at this very click. Let's get into the details of the game rules, to explain why this luck is necessary.

The game of minesweeper is played on a rectangular grid (indeed!) of $N$ rows and $M$ columns. Each cell of this grid either contains a single mine or is empty. The state of each cell is initially hidden from the player. The target of the player is to locate all the mines without accidentally exploding any of the mines. At the start of the game, all the cells are covered, thus the player has no clue about their states. During the game, a player makes two types of clicks: left or right, to any of the covered cells. When a user assumes that a cell is empty, he makes a left click and exposes the cell and some surrounding cells (check the next paragraph) in the process. When a user feels that a cell contains a mine, he or she makes a right-click to mark the cell as dangerous. But what happens if a user left-clicks on a mine cell? Well, the cell explodes and the game ends in defeat.

The above image shows a successfully finished Minesweeper game on a $10 \times 10$ grid with 16 mines.

When a player makes a left click on an empty cell, one or multiple cells are open using the following way:

1. If the clicked cell has mines in it, the mine explodes and the game ends.

2. If the clicked cell does not have any mines it, the clicked cell gets exposed. If any of the adjacent cells of the clicked cell have mines in them, then none of the adjacent cells are exposed. Only the clicked cell is exposed. The total number of mines that are placed in the adjacent cells is written on the clicked cell to help the player.

3. If none of the adjacent cells of the clicked cell have mines, then the clicked cell and the adjacent cells of the clicked cell get exposed. Each of the adjacent cells that are opened in this step will be considered as a clicked cell and further exploration will recursively take place from rule 2.

As you can see from the rules that, it is not possible for the player to determine any empty cells at the start. So, the player just has to make a random click to kick start the game. You can call it Minesweeper's version of "Leap of Faith". You can see some scenarios that can occur after the first click in notes.

You are a problem solver and you are wondering what are the odds of exposing one or more empty cells right at the first click of the game. If you are given N, M and X, the row, column and the total number of mines on the board, you would have to figure out the expected number of cells that would get exposed with the first click. If the first click is unfortunately over a mine, then no cell would get exposed as the game would end with that move.

Input

The first line of input contains $T$ ($1≤T≤100$), the number of testcases.

The following $T$ lines will be in the following format:

$N_i \space M_i \space X_i$ ($1 ≤ M_i, N_i, X_i ≤ 35$, $N \times M ≤ 35$)

Here, $N_i$ is the number of rows, $M_i$ is the number of columns and $X_i$ is the number of mines of the $i$-th case. The cases are generated in such a way that at most 20 percent of the cells of the board will have mines in them.

Output

For each testcase, please print the expected number of cells that would get exposed after the first click. Since the problem setter is scared of real numbers, please print the nearest integer of the result.

Sample

Input	Output
1 1 1 0	1

Imagine, in a $10 \times 10$ grid, the first click was made on cell $(5,5)$, where row and column indexes start from 1. If the clicked cell and the adjacent cells do not contain a mine, the following scenario can occur:

A similar scenario can occur in another configuration, where the first click was made on cell $(8,2)$, only this time, more cells are exposed:

The first click can only expose one cell:

In the most unfortunate case, a player can click any of the mine cells (marked with asterisks) right at the beginning to lose the game: