Maximum Colors in a Grid

You are given a rectangular grid with h rows and w columns and n available colors. Your task is to determine the maximum number of colors that can be used to paint the grid such that no two adjacent cells (vertically or horizontally) have the same color. Note that colors are used in pairs; therefore, the answer is the integer part of \(\frac{n}{2}\).

Formally: Given an integer \(n\), the maximum number of colors you can use is \[ \left\lfloor \frac{n}{2} \right\rfloor \]

Constraints: All input values are positive integers.

inputFormat

The first line of input contains a single integer T, the number of test cases. Each of the following T lines contains three space-separated integers representing h (number of rows), w (number of columns), and n (number of available colors), respectively.

Note: Although the grid dimensions h and w are provided, the answer is determined solely based on n.

outputFormat

For each test case, output a single line containing the maximum number of colors that can be used, which is \(\left\lfloor \frac{n}{2} \right\rfloor\).

## sample

3
3 3 4
4 5 6
5 5 2

2
3
1

</p>