Description

独立钻石是一种单人桌游。游戏在 $n$ 行 $m$ 列的棋盘上进行，棋盘上的每一格要么是空格，要么有一枚棋子。一开始，棋盘上共有 $k$ 枚棋子。

在游戏中，玩家可以选择一枚棋子，将它跳过相邻棋子到空格上，并移除被跳过的棋子。具体来说，令 $(i, j)$ 表示位于第 $i$ 行第 $j$ 列的格子，玩家可以执行以下四种操作。

给定一个初始的棋盘，求经过任意次操作（包括零次）之后，棋盘上最少能剩余几枚棋子。

Input Format

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 20$）表示测试数据组数。对于每组测试数据：

第一行输入三个整数 $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$ 行第 $y_i$ 列的格子里有一枚棋子。除了这 $k$ 个格子之外，其它格子一开始都是空格。这 $k$ 个格子的位置不会重复。

Output Format

每组数据输出一行一个整数，表示经过任意次操作（包括零次）之后，棋盘上最少能剩余几枚棋子。

【样例解释】

第一组样例数据解释如下。

对于第二组样例数据，由于初始棋盘不存在空格，因此无法进行任何操作。

对于第三组样例数据，由于棋盘不足三格，因此无法进行任何操作。

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