The Rubik's cube is the most popular toy in the world. Some even consider it as sport, since it requires dedication and training to master it. Also, there are competitions all over the world. There are many ways to compete: 3x3x3 (Rubik's cube), 2x2x2, 3x3x3 blindfolded, 4x4x4, etc. Usually, a speed cuber takes between 50 and 60 move to solve it, using Fridrich method. Fridrich (or CFOP) is a fast method, but requires a big effort for memorization. There are other methods like Roux (~48 moves), Petrus (~45 moves), ZZ (~50 moves) which requires fewer moves, but CFOP is still faster. There are other popular methods like Old Pochmann (~350 moves) ans M2/R2 (~150 moves). They are intended for blindsolving, since you can solve one piece at time.

 

A group of researches showed, by brute force, that any of the 43,252,003,274,489,856,000 positions of the Cube can be solved with at most 20 moves (half turn metric), now, "God Number is 20". The algorithm that always find the optimal solution for the cube is known as God's Algorithm, and it is just theoretical by these days.

 

Note: due to some abuses, in June 10th, 2016, a new judge was added. This one generates random cubes every time, although the n is fixed for every user. You can see the scrambles that generated the cubes you've got by clicking your score.

 

Input

First line, you have n<100, the number of cubes to be solved. You will be given n valid scrambled cube position, as in the sample, with default orientation (white on top, green on front).

 

The cube's faces are represented like:

 U

LFRB

 D

 

Ouput

You have to output the length of your solution, then the solution (at most 1000 face turns). Any valid sequence that solves the cube will be accepted. If you want to skip a particular cube, you have to print "-1" instead of the solution length. The penalty for that is 1000 moves, although if you skip all the cases, you will get WA. Every move must be in HTM, without cube rotations or double rotations, i. e., the only accepted moves are {U, F, R, ...} and {U2, U', F2, F', ...}.

 

Score

Score is the sum of the moves plus penaties.

 

Sample Input

3

      W W W

      W W W

      O O O

O O Y G G G W R R B B B

O O Y G G G W R R B B B

O O Y G G G W R R B B B

      R R R

      Y Y Y

      Y Y Y

      R W G

      W W W

      W W O

G R R B G W B B W O O W

O O O G G G R R R B B B

O O O G G G R R R B B B

      Y Y Y

      Y Y Y

      Y Y Y

      G R B

      O W G

      O O G

W G Y G Y W O R O W W R

Y O O B G G Y R W O B B

Y G R B Y B R W Y B R R

      Y R W

      W Y B 

      G B O

 

Sample Output

1

F'

7

R U R' U R U2 R'

-1

 

Sample Score

1008

 

(1+7+1000)

 

Special thanks to Mitch Schwartz, for helping in the custom judge, and Stefan Pochmann, for helping in some glitches.