You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

克露丝卡尔酱最近又想出了一个新点子。

“如果只能看到一半的信息，还能不能把另一半推出来呢？”她一边在草稿纸上画着小格子，一边自言自语。

社团里的后辈凑过来看了一眼：“诶？这不是扫雷吗？怎么只有上面一排呀？”

“这叫‘半信息扫雷’啦！”克露丝卡尔酱得意地扬了扬笔，“真正的推理，不是靠猜，而是靠必然性哦！”

她把那张只显示第一行信息的棋盘推到你面前，轻轻敲了敲桌面。

“来试试看吧～你能判断出第二行里，哪些格子一定是地雷，哪些一定是空格，哪些又根本无法确定吗？”

问题描述

你正在玩一个特殊的扫雷游戏。游戏在一个 $2$ 行 $n$ 列（$1 \le n \le 3 \times 10^5$）的网格上进行，每个格子要么是地雷，要么是空格。

你已经知道了第一行每个格子是地雷还是空格；如果该格子是空格，你还会看到一个数字，表示它周围八个方向相邻的格子中地雷的总数。

现在，你需要根据这些信息，推断第二行每个格子一定是地雷、一定是空格，还是无法确定。数据保证至少存在一种第二行的布局满足第一行的所有条件。

输入格式

本题有多组测试数据。

第一行一个正整数 $T$，表示数据组数。

接下来每一行表示一组数据，包含一个长为 $n$ 的字符串，其中第 $i$ 个字符表示第一行第 $i$ 个格子的情况：

• 如果该格子是地雷，则用字符 * 表示；
• 如果该格子是空格，则用一个数字字符 0 到 8 表示该格子周围八个方向相邻的格子中地雷的总数。

输出格式

对于每组数据，输出一个长度为 $n$ 的字符串，其中第 $i$ 个字符表示第二行第 $i$ 个格子的判断结果：

• 如果一定是地雷，输出 *；
• 如果一定是空格，输出 .；
• 如果无法确定，输出 ?。

样例 #1

样例输入 #1

6
*
111
12*21
11112221
*2*3*4*5*
*32*3*23*

样例输出 #1

?
.*.
??.??
??.??*??
...???***
*??.*.??*

提示

所有数据的 $n$ 之和 $\le 3\times 10^5$。数据保证至少存在一种第二行的布局满足第一行的所有条件。`