Нагадаємо деякі істотні для цієї задачі стандартні правила гри в шахи. Грають два гравці, один грає білими, інший чорними. Гра відбувається на шахівниці, тобто дошці ~8\times8~, стовпчики позначаються буквами від a до h зліва направо, рядки – цифрами від 1 до 8 знизу догори. Кожна клітинка дошки або порожня, або містить одну фігуру. Якщо фігура ~A~ (не пішак) може походити згідно з правилами у клітинку, зайняту чужою фігурою ~B~, то внаслідок такого ходу фігуру ~B~ б'ють, тобто знімають з дошки. Тому про всі клітинки, куди деяка фігура може походити, кажуть, що вони «під боєм» цієї фігури.

Королю заборонено ходити у клітинки, які перебувають під боєм будь-якої чужої фігури. Якщо один з гравців зробив такий хід, що король суперника опинився під боєм (це називають «шах»), суперник зобов'язаний відповісти таким ходом, щоб його король вже не був під боєм чужої фігури. Якщо такого ходу не існує, то це називають «мат».

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

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

Вхідні дані

Програма повинна прочитати спочатку кількість тестових блоків ~T~ (~1\leqslant T\leqslant 70000~), потім самі блоки. Кожен блок є окремим рядком, у якому записані позначення трьох клітинок, де розміщені білий король, білий ферзь і чорний король. Позначення клітинки складається із записаних разом букви вертикалі і номера горизонталі, позначення клітинок всередині рядка розділені одиничними пробілами.

Усі задані позиції гарантовано допустимі з точки зору шахових правил (зокрема, чорний король не під боєм).

Результати

Ваша програма повинна вивести для кожного тесту єдине число – мінімальну кількість ходів. Рахується лише кількість ходів білих (кількість ходів-відповідей чорних не додається).

Приклади

Вхід

2
a3 b3 a1
a3 e3 b1

Результат

1
2