Mine Number

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Every one once played the game called Mine Sweeping, here I change the rule. You are given an n*m map, every element is a '*' representing a mine, or a '.' representing any other thing. If I ask you what's the total number of mines around (i, j), you should check (i, j)'s up, down, left, right and also itself (if overstep the boundary, ignore it), if that position is a '*', you should add one to the total number of (i, j), and here I call the number Mine Number. For example, if the map is "..**.. ", we can get the Mine Number as "012210" easily, but here is the question, if I give you the Mine Number, can you tell me the original map?

Input

The input consists of multiple test cases.
The first line contains a number T, representing the number of test cases.
Then T lines follow. For each case, the first line contains two numbers n and m (1<=n, m<=20).representing the lines and rows. Then following n lines, each line contain m numbers each number represents the Mine Number.

Output

For each case, please print the case number (beginning with 1) and the original map which you reverted. The data guarantee there is only one result.

Sample Input

2
7 11
10010100101
21223221222
32354532323
32355532323
31235321333
21022201333
10001000111
5 6
001110
013431
014541
013431
001110

Sample Output

Case 1:
...........
*..*.*..*.*
*.*****.*.*
*.*****.*.*
*..***..*.*
*...*...***
...........
Case 2:
......
..***.
..***.
..***.
......

Hint

 

Source

2012年"浪潮杯"山东省第三届ACM大学生程序设计竞赛