### Description

#### Background

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 is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

#### Problem

Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

### Input

The input begins with a positive integer n in the first line. 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 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

### Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single 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 exist, you should output impossible on a single line.

### Sample Input

3 1 1 2 3 4 3

### Sample Output

Scenario #1: A1 Scenario #2: impossible Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4

Solution below . . .

class KnightTour { static int H, W; /* * Check if x,y are within the bounds of an H*W chessboard */ static boolean isSafe(int x, int y, int sol[][]) { return (x >= 0 && x < H && y >= 0 && y < W && sol[x][y] == -1); } /* * A utility function to print solution in the desired format */ static void printSolution(int sol[][]) { String[] solution = new String[H * W]; /* * The solution matrix (sol[][]) contains the solution as a * sequence of numbers from 0 to H * W - 1, showing the order * in which each square is visited. We need to convert that * to the output format specified by the problem description. */ for (int x = 0; x < H; x++) { for (int y = 0; y < W; y++) { char row = (char) ('A' + y); int col = x + 1; solution[sol[x][y]] = "" + row + col; } } StringBuilder sb = new StringBuilder(); for (String s : solution) { sb.append(s); } System.out.println(sb.toString()); } /* * This function solves the Knight Tour problem using backtracking. Backtracking * is not the most efficient solution but it does let us control the order in * which squares are visited. This is important because there can be multiple * solutions and the problem asks for the lexicographically first path. */ static boolean solveKT(int test) { int sol[][] = new int[H][W]; /* Initialization of solution matrix */ for (int x = 0; x < H; x++) for (int y = 0; y < W; y++) sol[x][y] = -1; /* * xMove[] and yMove[] define next moves for knight. xMove[] is for next value of * x coordinate yMove[] is for next value of y coordinate. The move arrays are * ordered so as to visit squares in lexicographical order. */ int xMove[] = { -1, 1, -2, 2, -2, 2, -1, 1 }; int yMove[] = { -2, -2, -1, -1, 1, 1, 2, 2 }; // Since the Knight is initially at the first square sol[0][0] = 0; System.out.println("Scenario #" + test + ":"); /* * Start from 0,0 and explore all tours using solveKTUtil() */ if (!solveKTUtil(0, 0, 1, sol, xMove, yMove)) { System.out.println("impossible"); return false; } else printSolution(sol); return true; } /* * A recursive utility function to solve Knight Tour problem */ static boolean solveKTUtil(int x, int y, int movei, int sol[][], int xMove[], int yMove[]) { int k, next_x, next_y; if (movei == H * W) return true; /* * Try all next moves from the current coordinate x, y */ for (k = 0; k < 8; k++) { next_x = x + xMove[k]; next_y = y + yMove[k]; if (isSafe(next_x, next_y, sol)) { sol[next_x][next_y] = movei; if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove)) return true; else sol[next_x][next_y] = -1;// backtracking } } return false; } public static void main(String args[]) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int test = 1; while (test <= T) { H = sc.nextInt(); W = sc.nextInt(); solveKT(test); if (test < T) System.out.println(); test++; } } }