考虑一个水平悬挂在空中的 $n \times m$ 矩形框架。最初，框架内紧密填充了 $n \times m$ 个 $1 \times 1$ 的方形积木。由于与框架及积木之间的摩擦力，积木处于稳定状态，不会掉落。

然而，积木可以被击落。当一块积木被击落时，其他剩余的积木也可能因为摩擦力不足以支撑它们而掉落。形式化地，如果一块积木被击中或变得不稳定，它就会掉落。当一块积木的左、右邻居中至少有一个已经掉落，且其前、后邻居中至少有一个也已经掉落时，该积木变得不稳定。在此定义中，框架可以被视为一个始终稳定的巨大积木。

现在，作为积木破坏者，你想要击落这些积木。形式化地，你将进行 $q$ 次移动。在第 $i$ 次移动中，你选择位置 $(x_i, y_i)$。如果所选位置仍有积木，你将其击落；否则，什么都不会发生。每次移动后，你必须等待直到没有不稳定的积木掉落，然后才能进行下一次移动。

例如，请看下图。框架大小为 $2 \times 2$，积木 $(1, 1)$ 和 $(1, 2)$ 已经掉落。如果我们击落积木 $(2, 2)$，它会掉落，随后最后剩下的积木 $(2, 1)$ 也会因为变得不稳定而掉落。

给定一系列移动操作，计算每次移动导致多少块积木掉落。特别地，如果某次移动没有发生任何事，则该次移动的答案为 0。

输入格式

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

第一行包含三个正整数 $n, m$ 和 $q$ ($1 \le n, m \le 2000, 1 \le q \le 100\,000$)，分别表示框架的尺寸和移动次数。

接下来的 $q$ 行，每行包含两个正整数 $x_i$ 和 $y_i$ ($1 \le x_i \le n, 1 \le y_i \le m$)，描述下一次移动的位置。

输出格式

对于每个测试用例，输出 $q$ 行。每行包含一个非负整数：表示对应移动导致掉落的积木数量。

样例

输入格式 1

2
2 2 3
1 1
1 2
2 2
4 4 6
1 1
1 2
2 1
2 2
4 4
3 3

输出格式 1

1
1
2
1
1
2
0
1
11