Chotu wanted to watch his favourite actor Rajnikanth’s movie “KABALI”. However since all the theatres were already booked on the opening day, he decided to watch it from the net. He quickly searched online and found a site which had the movie. He downloaded it and tried to open it. As usual it was locked. When he tried to open it, it did not ask him for a password, it asked him to solve a puzzle. As he is very eager to watch the movie, please help him to solve the puzzle.

The puzzle contains five squares and a pentagon. The vertices of the shapes are dots, 10 white and 5 black. The dots are numbered 1 to 15 and shapes are numbered 1 to 6(see the figure below). In order to solve the puzzle, you need to rotate the shapes, so that the five black dots form the vertices of the pentagon in the least number of rotations. Each figure can be rotated clockwise or anti-clockwise. One rotation involves moving each of the vertices to the adjacent place in the shape.

Input:

First line contains a number t denoting the number of test cases. Next t lines contain 15 numbers, 1 for white and 0 for black dots, in the order shown in the figure.

Output:

Print the minimum number of moves 'n' to solve the puzzle.

Example:

Input:

1

101100101101111

Output:

2

Problem Setter - Rohan