题目描述

马对一次又一次看到同样的黑白方块感到厌烦，决定环游世界。每当马移动时，它必须在一个方向上走两格，在垂直于这个方向的方向上走一格（马走日字）。马所在的世界就是他生活的棋盘（还是很有限嘛），这个棋盘的面积比普通的 $8×8$ 棋盘小，但它仍然是矩形的。

你能帮助这匹喜欢冒险的马找到一个路线，让他访问每个网格一次吗？他可以在棋盘的任何一个地方开始，并在任何一个网格结束旅程。

输入格式

输入第一行是一个正整数 $n$。以下行包含 $n$ 个测试用例。每个测试用例占一行，含两个正整数 $p$ 和 $q$，因此 $1≤p×q≤26$。这表示一个 $p×q$ 棋盘，其中 $p$ 表示行数 $1...p$，$q$ 表示列数，以字母表的前 $q$ 个字母 $ABC...$ 表示。

输出格式

每组测试数据的输出都以包含 scenario #i: 的行开始，其中 $i$ 是从 $1$ 开始的数据编号。然后输出一行路径，依次为马访问的方格，之后接一条空行。每个网格名称由一个大写字母和一个数字组成。

如果存在多条路径，请输出字典序最小的。

如果不存在这样的路径，则输出 impossible。

样例

3
1 1
2 3
4 3

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

提示