有 4 种类型的机器人：

• A：只能向下和向右移动。也就是说，位于点 $(x, y)$ 的机器人可以移动到点 $(x + 1, y)$ 或 $(x, y + 1)$。
• B：只能向下和向左移动。也就是说，位于点 $(x, y)$ 的机器人可以移动到点 $(x + 1, y)$ 或 $(x, y - 1)$。
• C：只能向上和向右移动。也就是说，位于点 $(x, y)$ 的机器人可以移动到点 $(x - 1, y)$ 或 $(x, y + 1)$。
• D：只能向上和向左移动。也就是说，位于点 $(x, y)$ 的机器人可以移动到点 $(x - 1, y)$ 或 $(x, y - 1)$。

网格中有 2 种类型的单元格：

• .（空地）：机器人可以自由放置并通过空地单元格。
• #（障碍）：机器人不能移动到障碍单元格。

给定一个值 $N$，构建一个大小为 $(N + 1) \times (N + 1)$ 的网格，使得每个单元格要么是空地，要么是障碍。然后放置 $N$ 个你想要的任意类型的机器人。机器人应该放置在空地单元格中，且任意两个机器人不能放置在同一个单元格中。

你还被给定了一棵树，其中每个非叶子节点都至少有 4 个邻居。设 $E$ 为边 $(x_i, y_i)$ 的集合。设 $S_i$ 为机器人 $i$ 可以移动到的单元格集合。必须满足以下条件：

• 对于所有 $(i, j) \in E$，必须满足 $S_i \cap S_j \neq \emptyset$。
• 对于所有 $(i, j) \notin E$，必须满足 $S_i \cap S_j = \emptyset$。

输入格式

• 第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。
• 接下来，对于每个测试用例：
  • 第一行包含一个整数 $N$ ($1 \le N \le 50$)。
  • 接下来 $N - 1$ 行，每行包含两个空格分隔的整数 $x_i, y_i$ ($1 \le x_i, y_i \le N$)。

输出格式

对于每个测试用例，按以下格式输出答案：

• 首先，输出 $N + 1$ 行，每行包含 $N + 1$ 个由 . 或 # 组成的字符。第 $i$ 行的第 $j$ 个字符（$1 \le j \le N + 1, 1 \le i \le N + 1$）应表示位置 $(i, j)$ 处的单元格类型。
• 然后，输出 $N$ 行，每行包含两个空格分隔的整数和一个字符 $A_i, B_i, C_i$（$1 \le A_i, B_i \le N + 1$；$C_i \in \{A, B, C, D\}$），其中 $(A_i, B_i)$ 是第 $i$ 个机器人放置的单元格，而 $C_i$ 是机器人的类型。注意，所有机器人必须放置在不同的单元格中。

样例

输入样例 1

1
5
1 2
1 3
1 4
1 5

输出样例 1

......
......
......
.##...
..#...
......
6 1 C
1 6 C
1 5 D
2 6 A
2 5 B

说明

图 1. 样例说明。