eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Шахматы

Шахматы

Ліміт часу 3 секунди
Ліміт використання пам'яті 256 MiB

Напомним некоторые существенные для данной задачи стандартные правила игры в шахматы. Играют два игрока, один играет белыми фигурами, другой чёрными. Игра происходит на доске 8x8, столбики обозначаются буквами от "a" до "h" слева направо, строки - цифрами от 1 до 8 снизу вверх. Каждая клетка доски или пустая, или содержит одну фигуру. Если фигура A (не пешка) может походить согласно правилам на клетку, занятую чужой фигурой B, то вследствие такого хода фигуру B бьют, т.е. снимают с доски. Поэтому обо всех клетках, куда некоторая фигура может походить, говорят, что они находятся "под боем" данной фигуры. Королю запрещено ходить в клетку, которая находится под боем любой чужой фигуры. Если один из игроков сделал такой ход, что король противника оказался под боем (это называется "шах"), противник обязан ответить таким ходом, чтобы его король уже не был под боем. Если такого хода не существует, то это называют "мат".

Король может ходить на одну клетку в любом из 8-ми направлений (влево, вправо, вперед, назад, в любом направлении по любой диагонали). Ферзь может ходить влюбом из 8-ми напрвлений на любое количество клеток, но не пересекая клеток, занятых фигурами.

Пусть на шахматной доске находится три фигуры: белый король, белый ферзь и черный король. Сейчас ход белых. За какое минимальное количество ходов они гарантированно смогут поставить мат? Чёрные будут делвть всё, допустимое правилами игры, чтобы избежать мата.

Вхідні дані

Программа долна прочитать число TEST_NUM - количество тестовых блоков, потом сами блоки. Каждый блок является отдельной строкой, в которой записаны три обозначения клеток, где находится белый король, белый ферзь и чёрный король соответственно, разделённые пробелом (обозначение клетки состоит из записанных слитно обозначения столбца и номера клетки).

Все заданые позиции гарантированно допустимы с точки зрения шахматных правил (например, чёрный король не под боем).

Вихідні дані

Ваша программа доджна вывести для каждого теста единственное число - минимальное количество ходов.

Приклад

Вхідні дані #1
2
a3 b3 a1
a3 e3 b1
Вихідні дані #1
1
2