如果一段区间（也可以是一个点）被所有区间都包含着,那我们就称这段区间为公共区间。
例如,[2,3]就是[1,4],[2,5],[1,3]的公共区间。[3]就是[1,3],[3,8],[1,8]的公共区间。[1,4],[5,8],[1,11]则没有公共区间。
现在,luo手里有一些区间,他想知道这些区间中是否存在着公共区间,如果没有,他可以选择将一些区间删除,例如[1,4],[5,8],[1,11]删除[5,8],剩下的区间为[1,4],[1,11],存在公共区间[1,4]。
现在他想知道他最少需要删除多少个区间,才能让剩余的区间存在公共区间。如果一开始就存在公共区间,直接输出 0 即可
输入
第一行为一个整数 t ,表示测试样例的组数
每组测试样例第一行为一个正整数 n ,表示一开始luo手上区间的数量
接下来 n 行,每行包括两个数 l , r ,表示区间的左端点和右端点
1 \leq t \leq 100
1 \leq n \leq 1000
1\leq l \leq r \leq 10^9
输出
输出共 t 行,分别表示每组测试样例的结果
样例
| 标准输入 复制文本 |
5 3 1 4 2 5 1 3 3 1 4 5 8 1 11 1 99999997 99999997 3 1 1 1 1 1 1 4 1 2 2 3 3 4 4 5 |
| 标准输出 复制文本 |
0 1 0 0 2 |