Migrated from Lutece 653 扫雷

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

扫雷是一种常见的游戏。现在我们想改变一下扫雷的规则。

在$n\times n$的方格地图上，地雷可以影响所有曼哈顿距离不大于$k$的位置，现在给出地图中雷的分布，用*代表地雷，用.代表无雷，请在所有无雷的位置填上对应的数字，表示能够影响到该位置的雷的数量。

在平面上，坐标$(x_1, y_1)$的点$P_1$与坐标$(x_2, y_2)$的点$P_2$的曼哈顿距离为：

$\left | x_1-x_2 \right |+\left | y_1-y_2 \right |$

Input

第一行是一个整数$T$($T\leq 10$)表示数据组数。

每组数据第一行包含两个数字$n$和$k$，$n$不大于$20$，$k$不大于$20$;

接下来包含$n$行，每行$n$个字符

*代表地雷，.代表无雷，字符中间不含空格。

Output

对于每组数据，输出相应的分布图，有雷的位置输出$-1$,无雷的位置输出对应的数字,每行的相邻两个数用一个空格隔开（每行的最后请不要输出多余的空格）。

Samples

2
2 1
*.
..
3 2
*..
...
*..

-1 1
1 0
-1 1 1
2 2 0
-1 1 1

Resources

第四届ACM趣味程序设计竞赛第三场（正式赛）