You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

是一种单人棋盘游戏，棋盘上有 $n$ 行和 $m$ 列。棋盘上的每个格子要么是空的，要么包含一个棋子。最初，棋盘上有 $k$ 个棋子。

在对局过程中，棋手可以选择一个棋子，将其跳过相邻的棋子进入空格，最后将跳过的棋子移走。更确切地说，假设 $(i,j)$ 是第 $i$ 行和第 $j$ 列上的单元格，那么棋手可以进行以下四种操作。

• 向上跳转 -选择满足以下所有条件的 $(i,j)$
• $i≥3$
• $(i,j)$,和$(i−1,j)$都包含一个棋子。
• $(i−2,j)$ 是空格。
• 将 $(i,j)$ 中的棋子跳到 $(i−2,j)$ ，并删除 $(i−1,j)$中的棋子。

• 向下跳转
• 选择满足以下所有条件的 $(i,j)$
• $i\le n-2$
• $(i,j)$,和$(i+1,j)$都包含一个棋子。
• $(i+2,j)$ 是空格。
• 将 $(i,j)$ 中的棋子跳到 $(i+2,j)$ ，并删除 $(i+1,j)$中的棋子。

• 向左跳转
• 选择满足以下所有条件的 $(i,j)$
• $j≥3$
• $(i,j)$,和$(i,j-1)$都包含一个棋子。
• $(i,j-2)$ 是空格。
• 将 $(i,j)$ 中的棋子跳到 $(i,j-2)$ ，并删除 $(i,j-1)$中的棋子。

• 向右跳转
• 选择满足以下所有条件的 $(i,j)$
• $j \le m - 2$
• $(i,j)$,和$(i,j+1)$都包含一个棋子。
• $(i,j+2)$ 是空格。
• 将 $(i,j)$ 中的棋子跳到 $(i,j+2)$ ，并删除 $(i,j+1)$中的棋子。

给定棋盘的初始状态，棋手可以执行任意次数(包括零次)的操作。计算棋盘上剩余棋子的最小可能数目。

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$ ( $1 \le T \le 10$ )，表示测试用例的数量。对于每个测试用例

第一行包含三个整数 $n$ 、 $m$ 和 $k$ ( $1 \le n, m \le 6$ , $1 \le k \le \min(6, n \times m)$ )，表示棋盘的行数和列数以及初始棋子数。

在接下来的 $k$ 行中， （第$i$行）包含两个整数 $x_i$ 和 $y_i$ （ $1 \le x_i \le n$ ， $1 \le y_i \le m$ ），表示在开始的 $x_i$ （第 $i$行）和 $y_i$ （第 $i$列）的单元格中有一颗棋子。除了这些 $k$ 单元格之外，其他单元格一开始都是空的。这些 $k$ 单元格的位置没有重复。

输出格式

对每个测试用例输出一行，其中包含一个整数，表示棋盘上剩余棋子的最小可能数量。

样例

输入

3
3 4 5
2 2
1 2
1 4
3 4
1 1
1 3 3
1 1
1 2
1 3
2 1 1
2 1

输出

2
3
1

样例解释

对于第一个样例

最终答案为 $2$

对于第二个样例，由于棋盘一开始不包含空格，棋手无法执行任何操作。

在第三个样例，由于棋盘上的单元格少于三个，棋手无法执行任何操作。

数据分布

$20\%$的数据, $2 \le n,m \le 4 , k \le 2$

$40\%$的数据, $4 \le n,m \le 6 , k \le 4$

$100\%$的数据, $4 \le n,m \le 6 , k \le 6$