WishingBone is always interested in e-puzzles. The other day his friend recommended one puzzle to him. It is called Spring Weekend.
The figure above shows a typical configuration. For each move, you choose one of the seven positions in the center while the six patterns around it adcance one step in the anticlockwise direction. Your goal is to make several moves to change the configuration to the one showed on the upper-right corner.
The rules being quite simple, WishingBone got quite dizzy over this puzzle. Help!
Input
The first line of input is a positive integer N <= 100, which is the number of test cases.
Each case contains two sets of configuration, one for the initial state and one for the desired state. One pattern is represented by less than 30 lower case Latin characters, with no other characters embedded.
Output
For each case, output one line with your solution.
Your solution should be one string of characters 1 to 7 (with no spaces embedded) indicating the positions you've chosen. The positions are defined as follows:
You should make as few moves as possible. If several solutions with minimal number of moves exist, you may choose to output any of them.
In case no solution exists or it needs more than 12 moves to achieve the goal, just print -1.
There will be at most 5 cases which need 12 or more moves.
Sample Input
1
redflower redflower redflower
redflower whiteflower dragonfly whiteflower
redflower redflower redflower redflower redflower
redflower redflower redflower redflower
redflower redflower redflower
redflower redflower redflower
redflower whiteflower whiteflower redflower
redflower redflower dragonfly redflower redflower
redflower redflower redflower redflower
redflower redflower redflower
Sample Output
5
