You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

在一个 $n*m$ 的矩形中，最初每个方格都是没有颜色的。

小明先后进行了 $q$ 次涂鸦操作，每次涂鸦都会给一个矩形区域涂上颜色。

对于一个矩形区域 $(x1,x2,y1,y2)$ , 左上角坐标为 $(x1,y1)$ ,右上角坐标为 $(x1,y2)$ ,左下角坐标为 $(x2,y1)$ ,右下角坐标为 $(x2,y2)$ 。

请问最后有多少个方格涂上了颜色？

Format

input

第一行一个整数 $T(1 ≤ T ≤ 100)$ ，表示测试用例数量。

每个测试用例：

第一行有 $3$ 个整数 $n , m , q$ ，其中 $1 \leq n*m \leq 10^6 ， 1 \leq q \leq 10^5$ ，保证所有测试用例 $n * m$ 的和不超过 $10^6$ ， $q$ 的和不超过 $5*10^5$ 。

从第 $2$ 行开始有 $q$ 行数据，对于第 $i+1$ 行，有 $4$ 个整数 $x1, x2, y1, y2 ,$ 表示第 $i$ 次涂鸦的矩形范围，其中 $1 \leq x1 \leq x2 \leq n , 1 \leq y1 \leq y2 \leq m $

output

对于每个测试用例，输出一行一个整数，表示最后涂上颜色的方格数。

Samples

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

1
11

Limitation

Time Limit: 1 second

Memory Limit: 256 MiB