Ходи ферзем!
На шаховій дошці 8х8 довільним чином розставлено 8 ферзів, по одному на кожній вертикалі, інших фігур на дошці немає. Ферзь може ходити на довільну кількість клітинок як по діагоналі, так і по вертикалі або горизонталі, але при цьому не може перестрибувати через інші фігури. Потрібно досягнути такої позиції у якій жоден ферзь не знаходится під ударом довільного іншого і зробити це за мінімальну кількість ходів.
Вхідні дані
В єдиному рядку задано спочатку натуральне число T (T < 6) – кількість тестових випадків. Далі через проміжок задано T блоків по 8 цілих чисел від 1 до 8 – номери горизонталей, на яких знаходиться ферзь з i-тої вертикалі. Вертикалі пронумеровано підряд.
Вихідні дані
Один рядок, який містить послідовність відповідних мінимальних кількостей ходів без проміжків.