题目描述

敌人追到了机关城，门口有 $n*m$ 的网格，在网格中人只能向下或向右相邻的格子移动，且不能走出去。

即 $(x,y)$ 只能移动到 $(x+1,y)$ 或 $(x,y+1)$。

所有人都要从 $(1,1)$ 进入，从 $(n,m)$ 走出，现在自己人已经安全逃出，敌人刚到 $(1,1)$ 位置。

现在网格中已经有 $k$ 个位置有障碍物。

小红想知道至少要在网格中再加几个障碍，才能让敌人不能从 $(1,1)$ 走到 $(n,m)$。

障碍物不能加在起点和终点上

输入格式

第一行一个整数 $T$ ，表示 $T$ 组数据。

第一行三个整数 $n,m,k$

接下来 $k$ 行，每行两个整数 $(x,y)$ 表示 $(x,y)$ 位置有障碍物。

输出格式

一个数字，表示需要再加几个障碍物

样例

1
5 3 5
1 2
1 3
2 2
2 3
3 2

1

样例说明

堵住 $(4,1)$ 就可以。

数据范围

对于 $20\%$ 的数据：$1\leq n,m\leq 5$

对于额外 $50\%$ 的数据：$n=2$

对于 $100\%$ 的数据：$1\leq n,m\leq 3000,1\leq k\leq n*m-2$。

$n,m$ 在 $T$ 组数据中的和分别 $\leq 3000$