2017 研究生直升面试机考(软件工程)

F. 涂黑板

单点时限: 3.0 sec

内存限制: 256 MB

林吉吉是一位富有艺术气息的绅士,读论文之余他最喜欢做的事情就是涂教室里的黑板。
黑板可以看作一块二维平面,林吉吉想要在黑板上涂黑 $n$ 个矩形,
第 $i$ 个矩形利用其左下角坐标 $(l_i,d_i)$ 和右上角坐标 $(r_i,u_i)$ 表示。

在涂黑了所有之后,林吉吉想要知道黑板上被涂黑的面积究竟有多少。

输入格式

第一行为数据组数 $T$

每组数据第一行为矩阵数目 $n$,接下来 $n$ 行为 $l_i,d_i,r_i,u_i$

数据约束:
对于 $40\%$ 的数据保证 $n\leq 10^2\quad 0\leq l_i \le r_i\leq 10^2\quad 0\leq d_i \le u_i\leq 10^2$
对于 $70\%$ 的数据保证 $n\leq 10^2\quad 0\leq l_i \le r_i\leq 10^9\quad 0\leq d_i \le u_i\leq 10^9$
对于所有数据保证 $T\leq 100\quad n\leq 10^3\quad 0\leq l_i \le r_i\leq 10^9\quad 0\leq d_i \le u_i \leq 10^9\quad$ 坐标为整数

输出格式

每组数据输出一行整数,黑板被涂黑的面积

样例

Input
2
2
1 1 10 10
5 5 15 15
2
1 1 5 5
10 10 15 15
Output
156
41