The territory of country P consists of $N \times M$ cities, arranged in a grid of $N$ rows and $M$ columns. The coordinates of the city in the $i$-th row and $j$-th column are denoted as $(i, j)$.

We consider two cities $(i_1, j_1)$ and $(i_2, j_2)$ to be adjacent if and only if $|i_1 - i_2| + |j_1 - j_2| = 1$.

The King wants to divide the cities into $K$ provinces, satisfying the following conditions:

• Each city belongs to exactly one province;
• Each province contains at least one city;
• For any two cities in the same province, there exists a path of cities within that province connecting these two cities, such that any two adjacent cities on the path are adjacent in the grid;
• Each city has exactly two adjacent cities that are in the same province as itself.

Please help the King provide a division scheme. If there are multiple solutions, you may output any one of them. If there is no solution, output NO.

Input

The first line contains a positive integer $T$, representing the number of test cases. For each test case:

• One line containing three positive integers $N, M, K$.

Output

For each test case:

• If there is no solution, output NO. Otherwise, output YES, followed by $N$ lines, each containing $M$ integers in the range $[1, K]$, representing the province to which each city is assigned.

Examples

Input 1

5
2 2 2
2 2 1
4 4 4
4 4 2
4 6 3

Output 1

NO
YES
1 1
1 1
YES
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
YES
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
YES
1 1 1 1 1 1
1 2 2 3 3 1
1 2 2 3 3 1
1 1 1 1 1 1

Constraints

For all test cases, $K \le NM$, $\sum NM \le 2 \cdot 10^5$.