Help johnny to solve this Puzzle Scenario

Little Johnny wants to play with his friends today. But his babysitter won't let him go! After a lot of begging, the heartless nanny gives him her brand new electronic puzzle and says: "If you solve the puzzle then you are free to go". Not being aware of Little Johnny's IT skills, the nanny leaves the kid alone.
Rapidly, Little Johnny sends you an e-mail asking for your help.
The puzzle consists of three hexagons as shown in the figure. Each vertex is painted black or white. Some of them belong to just one hexagon and some of them belong to more than one. Exactly four of them are painted black, and the other nine are white. The goal is to make the shared vertexes black by means of allowed moves: rotating a hexagon 60 degrees clockwise or counter-clockwise.
Can you help Little Johnny?

Input


  Input starts with an integer T, the number of puzzles to solve
  (1&lt;=T&lt;=100). T lines follow, each one having 13 binary digits,
  corresponding to the top-down, left to right labeling of the vertexes
  in the puzzle. A '0' means the i-th vertex is painted white, while a
  '1' means it is painted black.


output


  For each test case output M on a single line, the minimum number of
  moves required to solve the puzzle. Then print M lines, each one
  describing a move in the following manner: two space separated
  integers H and C, the rotated hexagon (upper left is 0, upper right 
  is 1, lower one is 2) and the direction (0 for counter-clockwise, 1
  for clockwise). If there is more than one solution, any will suffice.


Example 

Input sample:

1
0000000101011

output sample:

3

2 0

2 0

1 1

source Limit

50000 Bytes


time limit

1 sec


Winning constrain

shortest code with specified time limit wins!

I leave the question for five days to decide winner future answers after five days too welcome
Python, 307 chars

S={'0001001011000':[]}
for i in[0]*7:
 for s in dict(S):
  for m in range(6):S.setdefault(''.join(s[int(x,16)]for x in['2150483769abc','3106428759abc','0326159487abc','0421753986abc','01234587a6c9b','012345976b8ca'][m]),[m]+S[s])
for j in[0]*input():
 L=S[raw_input()];print len(L)
 for m in L:print m/2,m%2


Computes S which is a mapping from a state (a string just like the input) to a list of move numbers which solve the state.  Generates a complete S on startup (only 715 states), then looks up each input and prints the answer.

Moves are implemented using a string of hex digits indicating where each result vertex comes from.

Takes about 0.15 seconds regardless of how big the input is.