Problem D

Constrained Exchange Sort

Input : standard input

Output : standard output

 

Given a permutation of 12 letters 'A'-'L', you are invited to write a program to sort them in ascending order under the following set of constraints:

 

q       The only allowed operation is the exchange of letters between two locations (locations are numbered from 1 to 12).

q       The letter 'L' must be involved in each operation.

q       The letter 'L' at location l₁ can be swapped with the letter at location l₂ provided l₁ ~ l₂ = d_i and floor((l₁ - 1) / d_{i + 1}) = floor((l₂ - 1) / d_{i + 1})for i = 1 | 2 | 3, where (d₁, d₂, d₃, d₄) = (1, 3, 6, 12).

q       You must use the minimum number of exchange operations possible.

Input

The first line of the input file contains an integer representing the number of test cases to follow.

Each test case contains a permutation of the letters 'A'-'L' on a line by itself. It is guaranteed that the given permutation can be sorted in ascending order under the given set of constraints.

 

Output

For each test case first output the permutation number on a line by itself. The next line will contain a sequence of letters where the letter at location i represents the letter with which 'L' is swapped in the i-th exchange during the sorting process. Output an empty line after each test case.

Sample Input

2
BKLAIGFHEDCJ
LIFDHJAKEGCB

Sample Output

Permutation #1
EHCJGIKCJGIECBADFJGFJGHIFKEF

Permutation #2
AKIHCBJCBJEFCEFIKGJKHBEF