题目翻译：

背景描述

国际象棋中的骑士对日复一日地看着相同的黑白棋盘感到厌倦，决定开始一场环球旅行。骑士每次移动遵循"日"字形走法（横向$2$格纵向$1$格，或纵向$2$格横向$1$格）。骑士的世界就是他生活的棋盘，这个棋盘可能比标准的$8×8$棋盘要小，但仍然是一个矩形。你能帮助这位冒险的骑士制定旅行计划吗？

问题描述

寻找一条骑士路径，使得骑士能够访问棋盘的每一个方格恰好一次。骑士可以从任意方格开始和结束。

输入格式

• 第一行：正整数$n$（测试用例数量）
• 接下来$n$行：每个测试用例包含两个正整数$p$和$q（1 ≤ p×q ≤ 26）$
  • $p$表示棋盘的行数（数字$1$到$p$）
  • $q$表示棋盘的列数（字母$A$到第$q$个字母）

输出格式

对每个测试用例：

1. 第一行：$"Scenario$ #$i:"$（$i$从$1$开始）
2. 第二行：按字典序排列的第一条访问所有方格的路径，或$"impossible"$
3. 空一行

输入输出样例

输入样例1：

3
1 1
2 3
4 3

输出样例1：

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

题目来源

2005 年 TUD 编程竞赛，德国达姆施塔特