一家公司有 $n$ 名员工，每名员工 $i$ 都有一个空闲时间段 $[l_i, r_i]$（两个端点均为整数），在此期间他们可以参加会议。

公司正在组织一次团建活动，其中每对员工都需要进行一次一对一交流。为了让两名员工能够见面，他们的空闲时间段必须相交（即至少有一个公共点）。

员工可以通过更改其空闲时间段的端点来调整自己的日程安排。然而，重新安排日程是件麻烦事，将一个端点的时间从 $a$ 更改为 $b$ 会产生 $(a - b)^2$ 单位的沮丧值。较大的调整需要移动更多的预约，因此沮丧值呈二次方增长。调整后，每个时间段必须仍然合法（左端点小于或等于右端点，且两个端点仍为整数）。

你需要求出使每对员工都能找到时间见面所需的最小总沮丧值。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示员工人数。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$0 \le l_i \le r_i \le 10^6$），表示第 $i$ 位员工的空闲时间段。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最小总沮丧值。

样例

输入样例 1

3
3
6 8
0 2
1 7
2
1 3
2 4
2
1 1
100 100

输出样例 1

8
0
4901

说明

对于第一个样例测试用例，员工 1 可以将他/她的时间段从 $[6, 8]$ 调整为 $[4, 8]$，沮丧值为 $(6 - 4)^2 = 4$；员工 2 可以将时间段从 $[0, 2]$ 调整为 $[0, 4]$，沮丧值为 $(4 - 2)^2 = 4$。现在，这三个时间段 $[4, 8]$、$[0, 4]$ 和 $[1, 7]$ 两两相交，因此每对员工都可以进行交流。总沮丧值为 $4 + 4 = 8$。

对于第二个样例测试用例，两位员工的时间段已经相交，因此不需要进行任何调整。