Poddavki
When a game is available, exploring its variants, like a giveaway game, can be quite intriguing. In giveaway games, the goal is typically to lose according to the original rules. In this problem, we will focus on a chess giveaway scenario on a standard 8×8 board, where the white side has only a few pawns left, and the black side has a single queen.
In this setup, white moves first. On their turn, white chooses any of their pawns and moves it forward. If a pawn is on the second rank, it can move one or two squares forward (vertically); otherwise, it can only move one square. If a pawn reaches the eighth rank, it can no longer move (promotions are not allowed in this problem). A pawn captures one square diagonally, and capturing is mandatory; in this case, the game ends. If white has no legal moves, the game also ends.
Black moves their only queen. If black cannot capture any pawns, the game ends. Otherwise, black selects any of the pawns and captures it.
In this game, white aims to give away as many pawns as possible, while black aims to capture as few as possible. Your task is to determine the maximum number of pawns white can give away.
Input
The first line of the input file contains the number of test cases T (1 ≤ T ≤ 5). The following T lines each describe one test case. A test case is given by the number n (1 ≤ n ≤ 8) and n+1 coordinates of squares, where the first n specify the white pawns, and the last one specifies the position of the black queen.
No two white pawns are on the same file. The black queen is positioned differently from all the white pawns.
Output
For each test case, output the maximum number of pawns that white can give away before the game ends, assuming optimal play by both sides.