Шахматы
Напомним некоторые существенные для данной задачи правила игры в шахматы. Играют два игрока, один играет белыми фигурами, другой чёрными. Игра происходит на доске 8×8, столбики обозначаются буквами от "a" до "h" слева направо, строки - цифрами от 1 до 8 снизу вверх. Каждая клетка доски или пустая, или содержит одну фигуру. Если фигура A (не пешка) может походить согласно правилам на клетку, занятую чужой фигурой B, то вследствие такого хода фигуру B бьют, т.е. снимают с доски. Поэтому обо всех клетках, куда некоторая фигура может походить, говорят, что они находятся "под боем" данной фигуры. Если один из игроков сделал такой ход, что король противника оказался под боем (это называют "шах"), противник обязан ответить таким ходом, чтобы его король уже не был под боем. Если такого хода не существует, то это называют "мат".
Король может ходить на одну клетку в любом из 8-ми направлений (влево, вправо, вперед, назад, в любом направлении по любой диагонали). Ферзь может ходить в любом из 8-ми направлений на любое количество клеток, но не пересекая клеток, занятых фигурами.
Пусть на шахматной доске находится три фигуры: белый король, белый ферзь и черный король. Сейчас ход белых. За какое минимальное количество ходов они гарантированно смогут поставить мат? Чёрные будут делать всё, допустимое правилами игры, чтобы избежать мата.
Входные данные
Программа должна прочитать сначала натуральное число (TEST_NUM ≤ 70000) - количество тестовых блоков, потом сами блоки. Каждый блок является отдельной строкой, в которой записаны обозначения трёх клеток, где находятся белый король, белый ферзь и чёрный король. Обозначение клетки состоит из записанных слитно буквы вертикали и номера горизонтали, обозначения клеток внутри строки разделены единичным пробелом.
Все заданные позиции гарантированно допустимы с точки зрения шахматных правил (например, чёрный король не под боем).
Выходные данные
Ваша программа должна вывести для каждого теста единственное число - минимальное количество ходов.