“抢菜，然后去做核酸”已迅速成为 3 月 28 日凌晨上海突然封城后的口号。我们可以描述抢购（抢菜）的场景，以及在为控制中国主要商业和金融中心的新冠疫情而进行的疯狂竞标中，人们面临被锁在家门外的威胁。问题在于，当数百万人同时在手机上按下订单按钮时，服务器如何确定谁成功了。

处理如此大量的请求需要一个分布式系统。在分布式系统中，时间是一个棘手的问题，因为通信不是瞬时的：消息在网络中从一台机器传输到另一台机器需要时间。消息接收的时间总是晚于发送的时间，但由于网络中存在可变延迟，我们不知道具体晚了多少。这一事实有时使得在涉及多台机器时，难以确定事件发生的顺序。

此外，网络上的每台机器都有自己的时钟，这是一种实际的硬件设备：通常是石英晶体振荡器。这些设备并不完全精确，因此每台机器都有自己的时间概念，可能比其他机器稍快或稍慢。在一定程度上同步时钟是可能的：最常用的机制是网络时间协议（NTP），它允许根据一组服务器报告的时间来调整计算机时钟。而这些服务器又从更精确的时间源（如 GPS 接收器）获取时间。

现代计算机至少有两种不同类型的时钟：日历时钟（time-of-day clock）和单调时钟（monotonic clock）。日历时钟执行你直觉上对时钟的期望：它根据某种日历返回当前的日期和时间（也称为挂钟时间）。例如，Linux 上的 clock_gettime(CLOCK_REALTIME) 返回自纪元（Epoch）以来的秒数（或毫秒数）：即根据公历，从 1970 年 1 月 1 日午夜 UTC 开始计算，不计闰秒。有些系统使用其他日期作为参考点。日历时钟通常与 NTP 同步。

你或许能够以微秒甚至纳秒的分辨率读取机器的日历时钟。但即使你能获得如此细粒度的测量值，也不意味着该值具有如此高的精度。事实上，它很可能并不精确——如前所述，即使你每分钟与本地网络上的 NTP 服务器同步，不精确的石英钟的漂移也很容易达到几毫秒。使用公网上的 NTP 服务器，最佳精度可能在几十毫秒左右，而在网络拥塞时，误差很容易飙升至 100 毫秒以上。

因此，将时钟读数视为时间点是没有意义的——它更像是一个时间范围，即置信区间：例如，系统可能 95% 确信当前时间在分钟后的 10.3 到 10.5 秒之间，但它无法比这更精确。如果我们只知道时间 +/- 100 毫秒，那么时间戳中的微秒数字本质上是毫无意义的。

一个有趣的例外是 Google Spanner 中的 TrueTime API，它明确报告了本地时钟的置信区间。当你询问当前时间时，你会得到两个值：$[earliest, latest]$，即最早可能的时间戳和最晚可能的时间戳。基于其不确定性计算，时钟知道实际的当前时间位于该区间内。区间的宽度取决于多种因素，包括本地石英钟上次与更精确的时钟源同步以来经过了多长时间。

简而言之：Spanner 通过这种方式在数据中心之间实现了快照隔离。它使用 TrueTime API 报告的时钟置信区间，并基于以下观察：如果你有两个置信区间，每个区间由最早和最晚可能的时间戳组成（$A = [A_{earliest}, A_{latest}], B = [B_{earliest}, B_{latest}]$），并且这两个区间没有重叠（即 $A_{earliest} < A_{latest} < B_{earliest} < B_{latest}$），那么 B 肯定发生在 A 之后——毫无疑问。只有当区间重叠时，我们才不确定 A 和 B 发生的顺序。

现在我们使用 Spanner 作为解决方案，有数百万人正在抢购商品，每个人都被赋予了时钟的置信区间。服务器按时间顺序执行每个请求，并在区间重叠时终止。问题是，在服务器终止之前，有多少人可以买到他们的食物。

输入格式

第一行包含一个整数 $T$，表示有 $T$ 组测试数据。对于每组数据： 第一行包含一个整数 $n$，表示有 $n$ 个人。 接下来的 $n$ 行，每行包含 2 个整数 $earliest, latest$，表示时钟的置信区间。

数据范围：$T \le 10, 1 \le n \le 10^5, 0 \le earliest_i < latest_i \le 10^9$。

输出格式

对于每组数据，输出一个整数，表示答案。

样例

样例输入 1

2
3
1 2
3 4
5 6
3
1 2
2 3
1 5

样例输出 1

3
0