Cube and Caterpillar

Consider a cube of size 3 * 3 * 3. Let us number the 27 blocks in it as follows:
1 2 3
4 5 6
7 8 9

10 11 12
13 14 15
16 17 18

19 20 21
22 23 24
25 26 27
(The top layer is given first, followed by the middle, then the bottom one)

It is known that a strange caterpillar is stuck inside this cube. The length of its body is exactly 27, thus there is exactly one section of its body in each cell of the cube. The caterpillar's body is not necessarily straight; it may turn in any of the six directions (provided that the cell adjacent in that direction exists). You're given the information of which parts of the caterpillar's body turned in the respective cells, please find whether such a solution exists; if it does, output the lexicographically smallest one.

The first line of the input contains one integer, T, the number of test cases. T lines follow, each line containing 25 integers, describing the statuses of all parts of the caterpillar's body except head and tail, in the order from head to tail; if the i^th integer is non-zero, it means that the caterpillar's (i+1)^th part of body turned in its cell.

For each case, if a solution is found, please output three blocks in the format as indicated in the problem statement. 1 and 27 should be used to represent the head and the tail of the caterpillar, respectively. If no solution is found, please output one line containing “No solution” (without quotes).
Please follow the format as indicated in the sample output. Print a blank line after all cases except the last one.

2
0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Case 1:
1 2 3
6 5 4
7 8 9

18 13 12
17 14 11
16 15 10

19 20 21
24 23 22
25 26 27


Case 2:
No solution

2008 Asia Hangzhou Regional Contest Online