정사각형 부수기

성냥개비로 $n \times n$ 격자를 만든다. 모든 성냥개비의 길이는 1이고, 완전한 $n \times n$ 격자는 성냥개비 $2n(n+1)$개로 이루어진다. 예를 들어 완전한 $3 \times 3$ 격자는 성냥개비 $2 \times (3 \times 4) = 24$개로 이루어진다.

격자에는 다양한 크기의 정사각형이 있다. 정사각형의 크기는 한 변의 길이와 같다. 완전한 $n \times n$ 격자에서 크기가 $s$인 정사각형은 $(n-s+1)^2$개 있다. 예를 들어 완전한 $3 \times 3$ 격자에는 크기가 1인 정사각형 9개, 크기가 2인 정사각형 4개, 크기가 3인 정사각형 1개가 있다. 어떤 정사각형이 "존재한다"는 것은 그 정사각형의 둘레를 이루는 성냥개비가 모두 남아 있다는 뜻이다. (내부에 있는 성냥개비는 상관없다.)

성냥개비 번호 매기기. 성냥개비에는 1번부터 시작하여 왼쪽에서 오른쪽으로, 위에서 아래로 번호를 매긴다. 구체적으로, 맨 위 가로줄에 있는 가로 성냥개비 $n$개에 왼쪽부터 번호를 매기고, 이어서 그 바로 아래에 있는 세로 성냥개비 $n+1$개에 왼쪽부터 번호를 매긴다. 이렇게 가로줄(성냥개비 $n$개)과 세로줄(성냥개비 $n+1$개)을 번갈아 위에서 아래로 진행하며, 맨 아래 가로줄의 가로 성냥개비 $n$개로 끝난다. 예를 들어 완전한 $3 \times 3$ 격자에서 1~3번은 맨 위 가로 성냥개비, 4~7번은 그 아래 세로 성냥개비, ..., 22~24번은 맨 아래 가로 성냥개비이다.

완전한 격자에서 성냥개비 일부를 제거하면 일부 정사각형이 파괴되어 완전하지 않은 격자가 된다. 예를 들어 완전한 $3 \times 3$ 격자에서 12, 17, 23번 성냥개비를 제거하면 크기가 1인 정사각형 5개, 2인 정사각형 3개, 3인 정사각형 1개가 파괴되고, 크기가 1인 정사각형 4개와 2인 정사각형 1개가 남는다.

$2n(n+1)$개를 넘지 않는 성냥개비로 만든, 완전하거나 완전하지 않은 $n \times n$ 격자가 주어진다 ($n \le 5$). 이 격자에 남아 있는 모든 정사각형을 파괴하기 위해 제거해야 하는 성냥개비 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력은 $T$개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

첫째 줄에는 격자의 크기 $n$이 주어진다 ($1 \le n \le 5$). 둘째 줄에는 제거된 성냥개비의 개수 $k$가 먼저 주어지고, 이어서 제거된 성냥개비의 번호 $k$개가 주어진다. $k$가 0이면 완전한 격자가 주어진 것이고, 그렇지 않으면 완전하지 않은 격자가 주어진 것이다.

각 테스트 케이스에 대해, 주어진 격자에 남아 있는 모든 정사각형을 파괴하기 위해 제거해야 하는 성냥개비 개수의 최솟값을 한 줄에 하나씩 출력한다.