Lawn of the Dead

One day, a zombie came to the Lawn of the Dead, which can be seen as an $n\times m$ grid. Initially, he stood on the top-left cell, which is $(1,1)$.

Because the brain of the zombie was broken, he didn't have a good sense of direction. He could only move down from $(i,j)$ to $(i+1,j)$ or right from $(i,j)$ to $(i,j+1)$ in one step.

There were $k$ "lotato mines" on the grid. The $i$-th mine was at $(x_i,y_i)$. In case of being destroyed, he would never step into a cell containing a "lotato mine".

So how many cells could he possibly reach? (Including the starting cell)

The first line contains a single integer $t$ ($1\leq t \leq 20$), denoting the number of test cases.

The first line of each test case contains three integers $n, m, k$ ($2\leq n,m,k \leq 10^5$) --- there was an $n\times m$ grid, and there were $k$ "lotato mines" on the grid.

Each of the following $k$ lines contains $2$ integers $x_i,y_i$ $(1\leq x_i\leq n, 1\leq y_i\leq m)$ --- there was a "lotato mine" at $(x_i,y_i)$. It's guaranteed that there was no "lotato mine" at $(1,1)$ and no mines were in the same cell.

It is guaranteed that $\sum n\le 7\cdot 10^5 , \sum m\le 7\cdot 10^5$.

For each test case, output the number of cells he could possibly reach.

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

10

The cells that the zombie might reach are
(1,1), (1,2), (2,1), (2,2), (2,3), (2,4), (3,1), (3,3), (4,1), (4,2).

2021“MINIEYE杯”中国大学生算法设计超级联赛（4）