A Knight's Journey

Time limit1sMemory limit128 MB

Summary

Find the lexicographically smallest knight's tour that visits every square of a rectangular board with at most 26 squares exactly once.

Level: Medium6 of 10
Topics: Backtracking, DFS, Brute force, Implementation
Solved: No attempts yet

Problem

The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it moves two squares in one direction and one square perpendicular to that direction.

The world of a knight is the chessboard he lives on. Our knight lives on a chessboard that is smaller in area than a regular $8 \times 8$ board, but is still rectangular. Can you help this adventurous knight make its travel plans?

The eight possible moves of a knight.

Find a path in which the knight visits every square exactly once. The knight may start and end on any square of the board.

Input

The first line contains a positive integer $n$ . The following lines contain $n$ test cases.

Each test case consists of a single line with two positive integers $p$ and $q$ such that $1 \le p \cdot q \le 26$ . This represents a $p \times q$ chessboard, where $p$ is the number of distinct square numbers $1, \dots, p$ and $q$ is the number of distinct square letters. The letters are the first $q$ letters of the Latin alphabet: $A, \dots$

Output

For every scenario, first print a line containing "Scenario #i:", where $i$ is the scenario number, starting at 1. Then print, on a single line, the lexicographically first path that visits all squares of the chessboard using knight moves, followed by an empty line. The path is written on one line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.

If no such path exists, print impossible on a single line.

Examples1

Example 1

Input

Expected output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4