D. 推荐曲目
时间限制：2 秒
内存限制：512 MB

假设你在某个音频流媒体服务工作。该服务有 $n$ 个活跃用户和 $10^9$ 首曲目。用户可以喜欢曲目，服务基于这些喜欢来向他们推荐新曲目。

曲目编号从 $1$ 到 $10^9$。
已知第 $i$ 个用户喜欢的曲目构成一个区间 $[l_i, r_i]$。

定义用户 $j$ 是用户 $i$ 的 预测者（$j \neq i$），当且仅当用户 $j$ 喜欢所有用户 $i$ 喜欢的曲目（可能也喜欢其他曲目）。

定义某首曲目是用户 $i$ 的 强推荐曲目，当且仅当：

• 用户 $i$ 目前不喜欢这首曲目（即该曲目不在 $[l_i, r_i]$ 内），
• 但每个用户 $i$ 的预测者都喜欢这首曲目。

请对每个用户 $i$，计算其强推荐曲目的数量。
如果某用户没有预测者，则输出 $0$。

输入
第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数。
接下来 $t$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示用户数。

接下来的 $n$ 行，每行两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 10^9$），表示用户 $i$ 喜欢的曲目区间。

额外输入限制：所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出
对每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数表示用户 $i$ 的强推荐曲目数量（若无预测者则输出 $0$）。

样例
输入

4
3
3 8
2 5
4 5
2
42 42
1 1000000000
3
42 42
1 1000000000
42 42
6
1 10
3 10
3 7
5 7
4 4
1 2

输出

0
0
1
999999999
0
0
0
0
0
2
3
2
4
8

样例说明

• 第一个测试用例：

  • 用户 $1$ 无预测者；
  • 用户 $2$ 无预测者；
  • 用户 $3$ 有两个预测者：用户 $1$ 和用户 $2$；只有曲目 $3$ 被两人都喜欢且用户 $3$ 不喜欢。

• 第二个测试用例：

  • 用户 $2$ 是用户 $1$ 的预测者，所以除 $42$ 外的所有曲目都是用户 $1$ 的强推荐曲目。

• 第三个测试用例：

  • 用户 $1$ 有两个预测者：用户 $2$ 和用户 $3$，但没有一首曲目被他们喜欢且用户 $1$ 不喜欢。