나이트의 여행

나이트는 매번 똑같은 흑백 칸만 보는 것이 지겨워져서 세계 일주를 떠나기로 했다. 나이트는 한 번 움직일 때 한 방향으로 두 칸, 그리고 그 방향에 수직으로 한 칸 이동한다.

나이트의 세계는 그가 살고 있는 체스판이다. 이 나이트가 사는 체스판은 일반적인 $8 \times 8$ 판보다 작지만 여전히 직사각형 모양이다. 모험심 넘치는 이 나이트가 여행 계획을 세울 수 있도록 도와주겠는가?

나이트가 움직일 수 있는 여덟 가지 방법.

나이트가 모든 칸을 정확히 한 번씩 방문하는 경로를 찾아라. 나이트는 체스판의 어느 칸에서든 출발할 수 있고, 어느 칸에서든 끝낼 수 있다.

첫째 줄에 양의 정수 $n$이 주어진다. 이어지는 줄에는 $n$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 양의 정수 $p$와 $q$가 적힌 한 줄로 이루어지며, $1 \le p \cdot q \le 26$을 만족한다. 이는 $p \times q$ 크기의 체스판을 나타낸다. 여기서 $p$는 서로 다른 칸 숫자 $1, \dots, p$의 개수를, $q$는 서로 다른 칸 문자의 개수를 나타낸다. 칸 문자는 라틴 문자의 처음 $q$개, 즉 $A, \dots$ 이다.

각 시나리오의 출력은 "Scenario #i:" 형식의 줄로 시작한다. 여기서 $i$는 1부터 시작하는 시나리오 번호이다. 그다음, 나이트의 이동으로 체스판의 모든 칸을 방문하는 경로 중 사전순으로 가장 앞서는 경로를 한 줄에 출력하고, 그 뒤에 빈 줄 하나를 출력한다. 경로는 방문한 칸의 이름을 순서대로 이어 붙여 한 줄로 나타낸다. 각 칸의 이름은 대문자 하나와 그 뒤에 오는 숫자 하나로 이루어진다.

그러한 경로가 존재하지 않으면 impossible을 한 줄에 출력한다.