Піддавки
Зазвичай, коли є якась гра, дуже цікавою стає гра в піддавки, заснована на її правилах. У піддавках метою є навмисний програш за початковими правилами. У цій задачі ми розглянемо шахові піддавки на стандартній дошці 8×8, зокрема, ситуацію, коли у білих залишилося кілька пішаків, а у чорних — один ферзь.
У нашій ситуації першими ходять білі. Під час свого ходу білі обирають одного зі своїх пішаків і рухають його вперед. Якщо пішака стоїть на другому рядку, вона може ходити на одне або два поля вперед (по вертикалі), інакше — лише на одне поле. Якщо пішака доходить до восьмого рядка, вона більше не може ходити (перетворення у цій задачі не допускається). Пішака б'є на одну клітинку по діагоналі, причому взяття обов'язкове, і в цьому випадку гра закінчується. Якщо у білих немає допустимих ходів, гра також завершується.
Чорні ходять своїм єдиним ферзем. Якщо чорні не можуть з'їсти жодної пішаки, гра закінчується. Інакше чорні обирають одну з пішаків і з'їдають її.
У цій грі білі прагнуть віддати якомога більше пішаків, а чорні — з'їсти якомога менше. Ваше завдання — визначити, яку максимальну кількість пішаків можуть віддати білі.
Вхідні дані
У першому рядку вхідного файлу записано число тестових наборів T (1 ≤ T ≤ 5). Далі слідують T рядків, кожен з описом одного набору. Набір задається числом n (1 ≤ n ≤ 8) і n+1 координатами полів, де перші n задають білі пішки, а остання — положення чорного ферзя.
Жодні дві білі пішки не стоять на одній вертикалі. Чорний ферзь розташований у позиції, відмінній від усіх білих пішаків.
Вихідні дані
Для кожного з тестових наборів виведіть максимальну кількість пішаків, яку білі можуть віддати перш ніж гра закінчиться, за оптимальної гри обох сторін.