Ходи ферзём!

На шахматной доске 8х8 произвольным образом расставлено 8 ферзей, по одному на каждой вертикали, других фигур на доске нет. Ферзь может ходить на любое количество клеток как по диагонали, так и по вертикали или горизонтали, но при этом не может перепрыгивать через другие фигуры. Необходимо добиться такой позиции, в которой ни один ферзь не находится под боем любого другого, и сделать это за минимальное количество ходов.

Входные данные

В одной строке задано сначала натуральное число T (T < 6) - количество тестов. Далее через пробел задано T блоков по 8 целых чисел от 1 до 8 – номера горизонталей, на которых находится ферзь с i-той вертикали. Вертикали пронумерованы подряд.

Выходные данные

Одна строка, содержащая последовательность соответствующих минимальных количеств ходов без пробелов.