21818_Mine

Some mines are buried in the minefield. You need to find them all. The whole minefield is divided into n*m square regions. Each region has at most one mine. If there is no mine in a region, you can use a detector in this square area. The detector will tell you the total number buried mines in the eight regions around it. Now some regions of the entire minefield have been confirmed to be clear, and in these regions detector results are known too. The total number of mines in minefield is also known. And I hope you can determine the specific location of all buried mines.

There are multiple test cases.

The first line contains a case number t.

For each case, the first line contains three integers. The size of the minefield , n ( 2 < n < 10 ) and m ( 2 < m < 10 ), the total number of the mines buried in the minefield k ( 1 < k ≤ 10 ).

The next n lines contains m characters which describe the situation of the minefield. Each character corresponds to a region. The character '#' means the region is unknown, otherwise it is '0 '~ '8', showing the detector results in this region. The input data are legitimate, which means the results of detectors are accurate and reliable.

For each case, if we can 100% determine the specific location of all the mines, then output an n*m character matrix similar to the input. If there is no mines in a region, then output the result of the detector, otherwise output '*'. If you can not 100% determine all the specific location of mines, then output "NO" (quotes not included).

Output a blank line at the end of each case.

3
4 4 3
####
#111
111#
001#
3 3 2
##1
#21
#10
3 3 2
1#1
2#2
1#1

111*
*111
1111
001*

NO

1*1
222
1*1