H. Axington
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The city of Axington plans to expand!

Next to the city, there is a forested area that can be represented as a $$$n$$$-by-$$$n$$$ grid. Each cell is either empty or contains a tree. There is at least one tree.

Each day, there will be $$$k$$$ workers available to chop down trees. On any given day, you need to assign workers to trees in such a way that:

  • Each worker is assigned at most one tree to chop down, and no two workers are assigned the same tree.
  • Any tree designated to be chopped down must be connected to the edge of the grid.

Here, a tree is connected to the edge of the grid if it is possible to reach the edge of the grid by starting at the tree's cell, and moving only onto adjacent empty cells. Two cells are considered adjacent if they share a side.

Find the minimum number of days needed to chop all trees down, and construct one such plan.

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^4$$$).

The first line of each test contains $$$n$$$ and $$$k$$$, the size of the grid and the number of workers ($$$2 \le n \le 500$$$, $$$1 \le k \le 10^6$$$).

The next $$$n$$$ lines contain $$$n$$$ characters each, describing the grid. The $$$j$$$-th character in the $$$i$$$-th line is T if there is a tree at $$$(i,j)$$$, and . otherwise.

It is guaranteed that there is at least one tree in each grid.

It is guaranteed that the sum of $$$n^2$$$ over all tests does not exceed $$$250\,000$$$.

Output

For each test, output $$$n$$$ lines with $$$n$$$ tokens each.

The $$$j$$$-th token in the $$$i$$$-th line should be . if the cell $$$(i,j)$$$ is empty, and an integer $$$a_{i,j}$$$ otherwise  — denoting the day on which that tree should be cut down ($$$1 \le a_{i,j} \le n^2$$$).

If there are multiple possible answers, you can output any.

Example
Input
4
4 5
T T T .
T T T .
T T T .
. . . T
2 1
T T
T T
2 999
T T
T T
6 100
. T T T . .
T . T T . T
T T T T T T
T . T T T .
. T . . T T
. T T T T .
Output
2 2 2 .
2 2 1 .
1 1 1 .
. . . 1
4 3
2 1
1 1
1 1
. 1 1 1 . .
1 . 2 1 . 1
1 2 3 2 1 1
1 . 2 2 1 .
. 1 . . 2 1
. 1 1 1 1 .
Note

In the first test, note that we are not allowed to cut down the tree at $$$(2,2)$$$ on the first day because it is not connected to the edge.

In the second test, all trees are connected to the edge, but we have to cut them down one at a time because we only have one worker.

In the third test, we can cut down all trees within one day.