Disappearance No.0

Disappearance No.0은 컴퓨터 잡지 독자가 만든 퍼즐 게임이다. 이 게임의 목표는 게임판에 놓인 모든 돌을 이동으로 지우는 것이다. 게임판은 a부터 j까지의 알파벳으로 구분되는 열 개의 칸으로 이루어진다. 게임을 시작할 때 아래 그림의 예처럼 몇몇 칸에 돌이 놓여 있다. 각 돌에는 1부터 9까지의 숫자 하나가 붙어 있다. 같은 숫자가 붙은 돌이 여러 개 있을 수 있지만, 한 칸에 돌이 둘 이상 있을 수는 없다.

각 이동에서 플레이어는 게임판에 있는 돌 하나와 오른쪽 또는 왼쪽 방향을 고른다. 그러면 고른 돌이 붙어 있는 숫자만큼 고른 방향으로 움직인다. 돌이 가장 오른쪽이나 가장 왼쪽 칸에 닿으면 남은 횟수만큼 반대 방향으로 움직인다. 아래 그림은 돌의 움직임을 나타낸다.

가장 오른쪽 칸에 있는 돌을 오른쪽으로 움직이거나 가장 왼쪽 칸에 있는 돌을 왼쪽으로 움직이는 것은 무의미하므로 플레이어는 그렇게 움직이도록 고를 수 없다.

돌이 다른 돌이 있는 칸으로 움직이면 두 돌이 합쳐져 두 숫자의 합의 마지막 자리 숫자가 붙은 돌 하나가 된다. 예를 들어 9가 붙은 돌과 4가 붙은 돌이 합쳐지면 13(= 9 + 4)의 마지막 자리 숫자가 3이므로 3이 붙은 돌이 된다. 합쳐진 돌의 숫자가 0이면 그 돌은 사라진다.

여러분은 초기 상태가 주어졌을 때 게임판의 모든 돌을 지우는 가장 짧은 이동 순서를 출력하는 프로그램을 작성해야 한다.

첫째 줄에 테스트 케이스의 수를 나타내는 양의 정수 n이 주어진다. 다음 n개의 줄에는 각각 a부터 j까지의 칸의 초기 상태를 나타내는 열 개의 문자가 주어진다. 숫자는 그 칸에 그 숫자가 붙은 돌이 있음을 나타내고, 하이픈(-)은 그 칸에 돌이 없음을 나타낸다.

Sample Input의 첫 번째 테스트 케이스는 문제에 나온 예에 해당한다.

각 테스트 케이스마다 이동을 한 줄에 하나씩 출력한다. 각 이동은 두 문자로 이루어진다. 첫 번째 문자는 방향으로, R과 L은 각각 오른쪽과 왼쪽을 나타낸다. 두 번째 문자는 움직일 돌이 있는 칸의 이름이다. 여분의 공백이 있어서는 안 된다.

가능한 순서가 여러 개면 아무거나 출력해도 된다. 모든 돌을 지우는 순서가 없으면 “Impossible”을 한 줄에 출력한다. (따옴표는 출력하지 않는다.)

각 테스트 케이스 뒤에 빈 줄을 하나 출력한다.