Description

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

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

操作	描述	图例
向上跳	选择 \((i, j)\) 同时满足 \(i \ge 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 \ge 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)\) 中的棋子。

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

Input

有多组测试数据。第一行输入一个整数 \(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

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

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

Hint

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

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

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