Зачастую при наличии какой-то игры очень интересной оказывается игра в поддавки по её мотивам. В поддавках, как правило, целью игры является намеренный проигрыш относительно исходных правил. В этой задаче мы рассмотрим шахматные поддавки на обычной доске 8×8, а точнее, ситуацию, когда у белых остались только несколько пешек, а у чёрных — один ферзь.
В нашей ситуации первыми ходят белые. При своём ходе белые выбирают любую из своих пешек и двигают её вперед. Если пешка стоит на второй горизонтали, она может ходить на одно или на два поля вперед (по вертикали), иначе — только на одно поле. Если пешка доходит до восьмой горизонтали, она больше не может ходить (превращения в этой задаче не допускаются). Бьёт пешка на одну клетку по диагонали, причём взятие обязательно и в этом случае игра заканчивается. Если у белых нет допустимых ходов, то игра также заканчивается.
Чёрные ходят своим единственным ферзём. Если черные не могут съесть ни одной пешки, игра заканчивается. Иначе черные выбирают любую из пешек и съедают её.
В этой игре белые стремятся отдать как можно больше пешек, а чёрные — съесть как можно меньше. Ваша задача — узнать, какое максимальное количество пешек могут отдать белые.
В первой строке входного файла записано число тестовых наборов T (1 ≤ T ≤ 5). Далее следуют T строк, каждая с описанием одного набора. Набор задается числом n (1 ≤ n ≤ 8) и n+1 координатами полей, из которых первые n задают белые пешки, а последняя — положение чёрного ферзя.
Никакие две белые пешки не стоят на одной вертикали. Чёрный ферзь стоит в позиции, отличной от всех белых пешек.
Для каждого из тестовых наборов выведите максимальное количество пешек, которое белым удастся отдать прежде, чем игра закончится, при оптимальной игре обеих сторон.