L. Trails
time limit per test
3 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

BaoBao is taking a walk on an infinite two-dimensional plane. For each point $$$(x, y)$$$ on the plane where both $$$x$$$ and $$$y$$$ are integers, there is a bi-directional trail connecting points $$$(x, y)$$$ and $$$(x + 1, y)$$$, and another bi-directional trail connecting points $$$(x, y)$$$ and $$$(x, y + 1)$$$. What's more, there are $$$n$$$ additional bi-directional trails, where the $$$i$$$-th trail connects points $$$(x_i, y_i)$$$ and $$$(x_i + 1, y_i + 1)$$$.

BaoBao can only move along the trails. Let $$$f(x, y)$$$ be the smallest number of trails BaoBao has to pass if he wants to move from point $$$(0, 0)$$$ to point $$$(x, y)$$$. Given two integers $$$p$$$ and $$$q$$$, calculate

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

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains three integers $$$n$$$, $$$p$$$, and $$$q$$$ ($$$1 \le n \le 10^6$$$, $$$0 \le p, q \le 10^6$$$). Their meanings are described above.

For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^6$$$) indicating that the $$$i$$$-th additional trail connects points $$$(x_i, y_i)$$$ and $$$(x_i + 1, y_i + 1)$$$. It's guaranteed that $$$x_i \ne x_j$$$ or $$$y_i \ne y_j$$$ for all $$$i \ne j$$$.

It's guaranteed that the sum of $$$n$$$ of all test cases does not exceed $$$10^6$$$. Note that there is no constraint on the sum of $$$p$$$ or $$$q$$$.

Output

For each test case output one line containing one integer indicating the answer.

Example
Input
2
3 2 4
1 1
0 2
0 0
1 100 100
1000 1000
Output
34
1020100