P9700 [GDCPC 2023] Peg Solitaire

$\textit{Peg Solitaire}$ is a single-player boardgame on a chessboard with $n$ rows and $m$ columns. Each cell of the chessboard either is empty, or contains a chesspiece. Initially, there are $k$ chesspieces on the chessboard. During the game, the player can choose a chesspiece, jump it over an adjacent chesspiece into an empty cell, and finally remove the chesspiece which is jumped over. More precisely, let $(i, j)$ be the cell on the $i$-th row and the $j$-th column, the player can perform operations of the following four types.  Given the initial state of the chessboard, the player can perform the operations any number of times (including zero times). Calculate the minimum possible number of chesspieces remaining on the chessboard.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 20$) indicating the number of test cases. For each test case: The first line contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 6$, $1 \le k \le \min(6, n \times m)$) indicating the number of rows and columns of the chessboard and the initial number of chesspieces. For the following $k$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i \le n$, $1 \le y_i \le m$) indicating that there is a chesspiece in the cell on the $x_i$-th row and the $y_i$-th column at the beginning. Except from these $k$ cells, all other cells are empty at the beginning. The positions of these $k$ cells contain no duplicate.

For each test case output one line containing one integer indicating the minimum possible number of chesspieces remaining on the chessboard.

The first sample test case is explained as follows.  For the second sample test case, as the chessboard does not contain empty cell at the beginning, the player cannot perform any operation. For the third sample test case, as the chessboard has less than three cells, the player cannot perform any operation.