I Puzzle You

A Rubik’s Cube is a 3×3×3 cube, each of the six faces of which is covered by nine stickers. Each sticker is one of six solid colors white, red, blue, orange, green and yellow. Where white is opposite of yellow, blue is opposite of green and orange is opposite of red and red, white and blue are arranged in that order in a clockwise arrangement. An internal pivot mechanism enables each face to turn independently, thus mixing up the colors. At any time of game there are exactly 9 rectangles (3 × 3 × 1 boxes) to be rotated (left, right, front, back, top and bottom faces and three boxes in the middle). For the puzzle to be solved, each face must be returned to be consisted of cells of only one color. If we unwrap the cube, it will become like this: WWW WWW WWW R R R B B B O O O G G G R R R B B B O O O G G G R R R B B B O O O G G G YYY YYY YYY 123 456 789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 464748 495051 525354 The letters mean the colors on the sticker. In the left figure, ‘W’ means white, ‘R’ means red, ‘B’ means blue, ‘O’ means orange, ‘G’ means green and ‘Y’ means yellow. We can give each of the 54 stickers or faces of small cube a number from 1 to 54 according to the right figure above. When a rectangle is rotated the configuration of colors in all the adjacent faces (rectangles) changes. For example if we rotate the blue face in clockwise direction in the cube above, three white faces (7, 8 and 9) will move to the orange face (in 16, 28 and 40). You will be given the initial configuration of a Rubik’s cube in the form of a string, consisting of all the sticker color from the face 1 to 54. Find minimum number of moves (90 degree rotations) required to solve the puzzle (all the faces are one colored).

2/2 Input First line of the input will contain an integer T (T ≤ 100), number of test cases. Each of the next T lines will represent one test case. Each test case consists of a single string S of length 54 consisting of uppercase letters ‘B’, ‘G’, ‘O’, ‘R’, ‘W’ and ‘Y’. The string represents the current configuration of the Rubik’s cube and i-th character represents the color of i-th sticker defined above. Output For each test case, print the test case number starting from 1 and minimum number of rotations required to solve the cube. If the cube is unsolvable or requires more than 7 rotations to solve, print ‘Impossible’ instead of number of rotations. Sample Input 2 WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY WWWWWWRRRRRYBBBWOOGGGRRYBBBWOOGGGRRYBBBWOOGGGOOOYYYYYY Sample Output Case 1: 0 Case 2: 1