A Magic Circle

HUST Past Monthly Hard Problems Challenge Contest (2)

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 16

Solved: 8

Description

In the lead of Isun, HUST STI ACM Team all fascinated by magic cube. Today is the birthday of Gaewah, Isun bring a new thing as a gift to Gaewah. It is magic circle.

Show the magic circle in a surface like this

original status of magic circle

But actually, the red gird is connected to the green one, so as the blue and yellow.

There are 8 operates for the magic circle.

If we sign the operate as 1,2,3……,8，from the original status, we can get the status below from 1 step.

Now gaewah disarray the magic circle.He want the smallest step to get a status, that four color on the center are the same color.Can you help him?

Input

The first line just a number t,indicate the number of test case.(1<=t<=10000)

For each case: the format like sample input, each number means a color, there are only 1,2,3,4,5 will appear in the input and each color exactly appear 4 times.

There are a blank line between each test case.

Output

For each case, output a sentence “The minimum steps is :”,then a integer.

if the input status is the answer, just output “Do not need move!”

sample input

2

    1 2

    3 4

5 1 2 3 4 5

1 2 3 4 5 1

    2 3

    4 5



    5 1

    1 5

5 4 2 2 4 4

1 3 2 2 4 5

    1 3

    3 3

sample output

The minimum steps is :4

Do not need move!

hint

source

Hust Monthly 09.08.21/Zehua HONG

Submit