题目描述

小明参加了一场大型的“欺诈游戏”，现在已经来到了最后一轮环节，最后一个环节还剩下 $n$ 个人，编号为 $1,2,\dots,n$。小明只要胜出，就能获得终极大奖 $1000$ 万。

本轮游戏开始前，主办方会在大屏幕放映随机生成的 $n$ 个人的分数，也就是说大家都知道彼此的分数。在看完所有人的分数后，主办方要求每一个参与游戏的人，都说一句“有几个人分数比我高，有几个人分数比我低”，当然，这句话可以不是真实的，可以说谎。

每个人说完后，主办方收集了每一个人的回答，具体地，编号为 $i$ 的人说的是：“有 $a_i$ 个人分数比我高，有 $b_i$ 个人分数比我低”。

现在问：$n$ 个人中最少有几个人在说谎？（即存在一个真实的排名，使得与该排名不一致的回答人数最少。）

输入格式

本题有多组测试数据。

• 第一行包含一个整数 $t$，表示测试数据组数。

• 对于每组测试数据：

  • 第一行包含一个整数 $n$，表示参与最后一轮游戏的人数。
  • 接下来 $n$ 行，每行包含两个非负整数 $a_i$ 和 $b_i$（分别表示第 $i$ 个人所说的“比我高的人数”和“比我低的人数”）。

保证每组数据的输入满足题目约束。

输出格式

对于每组测试数据，输出一行一个整数，表示在本轮游戏中，说谎人数的最少可能值。

样例输入 1

1
3
2 0
0 2
2 2

样例输出 1

1

样例 2

见选手目录下的 liar/liar2.in 与 liar/liar2.ans。 该测试用例满足测试点 $1\sim 3$ 的约束条件。

样例 3

见选手目录下的 liar/liar3.in 与 liar/liar3.ans。 该测试用例满足测试点 $4\sim 6$ 的约束条件。

样例 4

见选手目录下的 liar/liar4.in 与 liar/liar4.ans。 该测试用例满足测试点 $7\sim 10$ 的约束条件。

说明

样例解释

假设第 $1$ 句话是真话（有 $2$ 个人比他高），则编号为 $1$ 的人排名第 $3$；同理若第 $2$ 句话是真话，则编号为 $2$ 的人排名第 $1$。由此可确定三个人的排名为 $2,3,1$。在该排名下，第 $3$ 号的回答与排名不符，因此第 $3$ 号在说谎，总共说谎人数为 $1$。枚举可知 $1$ 是最小可能值。

数据范围

对于 $100\%$ 的数据，满足：

• $1 \le t \le 3$；
• $1 \le n \le 10^5$；
• $0 \le a_i+b_i \le 2\times 10^5$。

各测试点的附加限制如下表所示：

大样例

点击下载