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