Chiaki 拥有一个边长为 $n$ 的等边三角形。她想用角度为 $60^\circ$ 和 $120^\circ$ 的单位菱形来覆盖这个三角形。

边长为 4 的等边三角形，以及从左到右编号为 1 到 3 的三种菱形。

Chiaki 很快发现这是一个不可能完成的任务。于是她从等边三角形中切掉了恰好 $n$ 个向上的小三角形。现在，Chiaki 想知道是否可以用菱形覆盖剩下的形状。下图是 $n = 4$ 时的一个覆盖示例。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 5000$)，表示等边三角形的边长。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $i$ 的二进制字符串 $s$，其中 $s_j = 0$ 表示第 $j$ 个向上的三角形被切掉了。

保证所有测试数据的 $n$ 之和不超过 $5000$。

输出格式

对于每组测试数据，输出一个合法的覆盖方案。一个合法的覆盖方案包含 $n$ 行，第 $i$ 行包含 $i$ 个字符。第 $j$ 个字符应为：

• ‘-’：如果第 $j$ 个向上的三角形被切掉了。
• ‘1’：如果第 $j$ 个向上的三角形被第一种菱形覆盖。
• ‘2’：如果第 $j$ 个向上的三角形被第二种菱形覆盖。
• ‘3’：如果第 $j$ 个向上的三角形被第三种菱形覆盖。

如果无解，则输出 “Impossible!”（不含引号）。

样例

输入 1

1
4
0
11
010
1101

输出 1

-
21
-3-
33-1