题目描述

堡堡正在一块无穷大的二维平面上散步。对于平面上每个满足 $x$ 和 $y$ 均是整数的点 $(x, y)$，都有一条双向小径连接点 $(x, y)$ 和 $(x + 1, y)$，还有另一条双向小径连接点 $(x, y)$ 和 $(x, y + 1)$。另外，还有 $n$ 条额外的双向小径，其中第 $i$ 条连接点 $(x_i, y_i)$ 和 $(x_i + 1, y_i + 1)$。

堡堡只能沿着小径移动。令 $f(x, y)$ 表示堡堡从点 $(0, 0)$ 出发到达点 $(x, y)$ 最少需要经过几条小径。给定两个整数 $p$ 和 $q$，计算

$$\sum\limits_{x = 0}^p \sum\limits_{y = 0}^q f(x, y) $$

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入三个整数 $n$，$p$ 和 $q$（$1 \le n \le 10^6$，$0 \le p, q \le 10^6$）。它们的含义如上所述。

对于接下来的 $n$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$0 \le x_i, y_i \le 10^6$）表示第 $i$ 条额外小径连接点 $(x_i, y_i)$ 和 $(x_i + 1, y_i + 1)$。保证对于所有 $i \ne j$ 有 $x_i \ne x_j$ 或 $y_i \ne y_j$。

保证所有数据 $n$ 之和不超过 $10^6$。请注意，$p$ 与 $q$ 之和没有限制。

输出格式

每组数据输出一行一个整数表示答案。

2
3 2 4
1 1
0 2
0 0
1 100 100
1000 1000

34
1020100