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