Destroying Squares

Matchsticks are used to build an $n \times n$ grid. Every matchstick has length 1, and a complete $n \times n$ grid is made of $2n(n+1)$ matchsticks. For example, a complete $3 \times 3$ grid is made of $2 \times (3 \times 4) = 24$ matchsticks.

The grid contains squares of various sizes. The size of a square equals the length of its side. A complete $n \times n$ grid contains $(n-s+1)^2$ squares of size $s$. For example, a complete $3 \times 3$ grid has 9 squares of size 1, 4 squares of size 2, and 1 square of size 3. A square "exists" when all of the matchsticks that form its perimeter are still present. (The matchsticks in its interior do not matter.)

Numbering the matchsticks. The matchsticks are numbered starting from 1, from left to right and from top to bottom. Concretely, the $n$ horizontal matchsticks of the top row are numbered from the left, and then the $n+1$ vertical matchsticks directly below them are numbered from the left. This alternation of a horizontal line ($n$ matchsticks) and a vertical line ($n+1$ matchsticks) continues downward, ending with the $n$ horizontal matchsticks of the bottom row. For example, in a complete $3 \times 3$ grid, numbers 1-3 are the top horizontal matchsticks, 4-7 the vertical matchsticks below them, ..., and 22-24 the bottom horizontal matchsticks.

Removing some matchsticks from a complete grid destroys some squares, producing an incomplete grid. For example, removing matchsticks 12, 17, and 23 from a complete $3 \times 3$ grid destroys 5 squares of size 1, 3 squares of size 2, and 1 square of size 3, leaving 4 squares of size 1 and 1 square of size 2.

You are given a complete or incomplete $n \times n$ grid built from at most $2n(n+1)$ matchsticks ($n \le 5$). Write a program that finds the minimum number of matchsticks that must be removed to destroy every square remaining in the grid.

The input consists of $T$ test cases. The first line contains the number of test cases $T$. Each test case consists of two lines.

The first line contains the grid size $n$ ($1 \le n \le 5$). The second line first contains $k$, the number of removed matchsticks, followed by the $k$ numbers of the removed matchsticks. If $k$ is 0 the grid is complete; otherwise it is incomplete.

For each test case, output on its own line the minimum number of matchsticks that must be removed to destroy every square remaining in the given grid.