Coco 想要将一块大小为 $M \times N$ 的巧克力分割成 $1 \times 2$ 或 $2 \times 1$ 的大小进行出售。然而，有一天 Coco 的 $K$ 个朋友来拜访，并吃掉了其中的 $K$ 个 $1 \times 1$ 的巧克力格子。请告诉 Coco，在分割剩下的巧克力时，最多可以获得多少块巧克力。

输入格式

第一行包含测试数据组数 $T$。接下来依次给出 $T$ 组测试数据。

每组测试数据的第一行包含三个整数 $M$，$N$ 和 $K$。其中 $M$ 表示巧克力的宽度（列数），$N$ 表示巧克力的高度（行数）。

接下来的 $K$ 行，每行包含两个整数 $m$ 和 $n$，表示被朋友吃掉的巧克力格子的位置，分别为横坐标 $m$ 和纵坐标 $n$。

最左上角的格子坐标为 $(1, \,1)$，且所有被吃掉的巧克力格子位置互不相同。

输出格式

对于每组测试数据，输出一行，表示将剩余巧克力分割后最多可以获得的 $1 \times 2$ 或 $2 \times 1$ 巧克力的数量。

样例

样例输入 1

4
4 4 0
4 4 2
1 1
4 4
4 4 4
1 1
4 4
2 3
3 4
4 4 4
1 2
2 1
3 3
4 4

样例输出 1

8
6
6
5

说明

$1 \le T \le 1000$，$4 \le M, N \le 1000$，$0 \le K \le 4$，$M$ 和 $N$ 是 $4$ 的倍数，$1 \le m \le M$，$1 \le n \le N$。