SP135 MAWORK - Men at work

你所居住的小镇可以看作一个 $N$ 行 $N$ 列的网格。你的家位于西北角 $(1,1)$，而你的公司位于东南角 $(N,N)$。 每天早上你都要开车到你的公司。不幸的是，小镇上的所有路都在维修！幸运的是，当地管理部门意识到这可能会造成麻烦，所以他们对道路承包商实施了严格的规定：道路必须在恰好一半的时间内停止维修。但是，承包商可以自由安排工作时间。具体的： - 第 $i$ 行第 $j$ 列的道路有一个固定参数 $a_{i,j}$，表示周期长度 - $0$ 时刻的时候，道路进入初始状态 - 那之后，每 $a_{i,j}(0\le a_{i,j}\le 9)$ 时刻，道路的状态切换一次（从维修中变为可通行或者从可通行变为维修中） - **注意，如果 $a_{i,j}=0$，表示道路永远维持初始状态不会改变** 你会在 $0$ 时刻离开家，每一单位时间可以选择向东、南、西、北四个方向移动一步或者留在原地不动。任意时刻，你所在的位置必须在小镇内且是可通行的。 编写一个程序，在给定道路网络和承包商时间表的描述的情况下输出从家到工作所需的最短时间。 你想知道，你最早什么时候到达公司？

输入的第一行包含一个数字 $T$，表示数据组数。对于每组数据： 第一行是一个数字 $N$。 接下来 $N$ 行是一个大小为 $N\times N$ 的字符串数组。表示 $0$ 时刻时每条道路的状态。具体的，`.` 代表可通行，而 `*` 代表维修中。 最后 $N$ 行，每行 $N$ 个字符，表示承包商的时间表，即 $a_{i,j}$。再次强调，如果一个位置为 $0$，则表示相应的道路状态不会改变。

对于每个测试样例，输出只有一行，从你家到公司的最快时间。如果永远无法到达，请输出 `NO`。

对于全部数据，保证： $T\le 10$，$2\le n\le 25$。