该国家包含 $N$ 座城市，编号从 $1$ 到 $N$，以及 $M$ 条连接城市对的无向道路。现有若干询问。每个询问由两个数字 $L$ 和 $R$ 表示，意味着所有编号在 $L$ 和 $R$ 之间（包含 $L$ 和 $R$）的城市是安全的，而其他城市是不安全的。我们定义城市 $A$ 可以到达城市 $B$，当且仅当它们都是安全的，且存在一条从 $A$ 到 $B$ 的路径，使得路径上的所有城市都是安全的。

对于每个询问，你需要计算在给定询问条件下，能够互相到达的城市对的数量。

输入格式

第一行包含一个数字 $T$，表示测试用例的数量。 对于每个测试用例，第一行包含三个数字：上述的 $N$、$M$ 和 $Q$。 接下来的 $M$ 行，每行包含两个整数 $X, Y$ ($X \neq Y$)，表示城市 $X$ 和城市 $Y$ 之间有一条道路 ($1 \le X, Y \le N$)。 接下来的 $Q$ 行，每行包含两个数字 $L, R$，表示一个询问 ($1 \le L, R \le N, L \le R$)。

$T \le 5, N, M \le 50000, Q \le 100000$

输出格式

对于每个测试用例，输出 $Q$ 行，每行包含对应询问的答案。

样例

输入 1

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

输出 1

6
1
10
0