Little Cyan Fish 是逻辑谜题的爱好者。今天，他正在玩一种经典谜题“Summon”的特殊版本。

考虑一个 $2$ 行 $2n$ 列的网格。令 $(x, y)$ 表示第 $x$ 行第 $y$ 列的单元格。网格被划分为 $n$ 个区域，每个区域都是一个 $2 \times 2$ 的正方形。具体来说，对于每个 $1 \le i \le n$，第 $i$ 个区域 $R_i$ 包含恰好 4 个单元格：$(1, 2i - 1)$、$(1, 2i)$、$(2, 2i - 1)$ 和 $(2, 2i)$。

图 4：$n=5$ 时的网格示例。每个区域的边界用粗线标出。

该谜题的任务是在部分单元格中填入 $1$ 到 $2$ 的数字，需满足以下规则：

• 对于每个区域 $R_i$ ($1 \le i \le n$)，它必须恰好包含 $1$ 到 $2$ 中的每个数字各一次。
• 相同数字的单元格不能接触，即使是斜向接触也不行。

图 5：一种合法的填数方案

图 6：一种不合法的方案：标红的数字相互接触

图 7：一种不合法的方案：区域 $R_4$ 不包含数字 2。

方案的价值定义为第一行中形成的数字之和。具体来说，第一行中连续的数字块从左到右读取形成数字，所有这些数字的和即为该方案的价值。

图 8：在此方案中，价值为 $1 + 212 + 2 = 215$

现在，Little Cyan Fish 给了你一个未完成的谜题：一个 $2 \times 2n$ 的网格，其中包含一些预填的数字。你的任务是在一些空单元格中填入数字，以获得该谜题的一个价值最大的合法解。

输入格式

输入包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 100\,000$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)。 接下来的两行每行包含 $2n$ 个字符，表示谜题的初始状态。每个字符要么是 $1$ 到 $2$ 之间的数字（表示预填的数字），要么是字符 ?（表示空单元格）。 保证所有测试用例中 $n$ 的总和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，如果没有可能的方案，输出一行字符串 “impossible”（不含引号）。 否则，第一行输出一个整数，表示方案的最大价值。 接下来的两行输出你找到的方案。每行应包含 $2n$ 个字符，表示你的解。每个字符要么是 $1$ 到 $2$ 之间的数字（表示填入数字的单元格），要么是 $0$（表示空单元格）。如果存在多个价值相同的最优解，你可以输出其中任意一个。

样例

输入 1

5
2
?1??
??1?
4
1???????
???2???2
5
??????????
??????????
6
1212????????
????????1212
7
?2?1?????1?2??
?????1???????2

输出 1

impossible
242
12101210
00020002
2121212121
2121212121
0000000000
12121212
121212120000
000000001212
21
12010202010201
00020101020102