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

Поддавки

Поддавки

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Зачастую при наличии какой-то игры очень интересной оказывается игра в поддавки по её мотивам. В поддавках, как правило, целью игры является намеренный проигрыш относительно исходных правил. В этой задаче мы рассмотрим шахматные поддавки на обычной доске 8×8, а точнее, ситуацию, когда у белых остались только несколько пешек, а у чёрных — один ферзь.

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

Чёрные ходят своим единственным ферзём. Если черные не могут съесть ни одной пешки, игра заканчивается. Иначе черные выбирают любую из пешек и съедают её.

В этой игре белые стремятся отдать как можно больше пешек, а чёрные — съесть как можно меньше. Ваша задача — узнать, какое максимальное количество пешек могут отдать белые.

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

В первой строке входного файла записано число тестовых наборов T (1T5). Далее следуют T строк, каждая с описанием одного набора. Набор задается числом n (1n8) и n+1 координатами полей, из которых первые n задают белые пешки, а последняя — положение чёрного ферзя.

Никакие две белые пешки не стоят на одной вертикали. Чёрный ферзь стоит в позиции, отличной от всех белых пешек.

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

Для каждого из тестовых наборов выведите максимальное количество пешек, которое белым удастся отдать прежде, чем игра закончится, при оптимальной игре обеих сторон.

Пример

Входные данные #1
3
5 a2 c2 d2 e3 h4 b6
2 a2 h2 g3
2 a7 h7 a8
Выходные данные #1
5
0
1
Источник III Международная Летняя школа программирования 2012 г. Севастополь