AT_tupc2024_q Make Intervals Disjoint

$ N $ 個の半開区間が与えられます。 $ i $ 個目の半開区間は整数 $ L_i,R_i $ を用いて $ [L_i,R_i) $ と表されます。 あなたは以下の操作を任意の回数( $ 0 $ 回も可)行う事が出来ます。 - $ 2N $ 個の整数 $ L_1,R_1,L_2,R_2,\dots,L_N,R_N $ のうち $ 1 $ つを選び、値を $ 1 $ 増やすか $ 1 $ 減らす。 あなたの目標は、 $ N $ 個の半開区間 $ [L_1,R_1), [L_2,R_2),\dots,[L_N,R_N) $ を互いに交わらないようにすることです。 より厳密には、 $ 1\le i\lt j\le N $ なる全ての整数の組 $ (i,j) $ について、 「 $ L_i\le x\lt R_i $ かつ $ L_j\le x\lt R_j $ を満たす実数 $ x $ が存在しない」ようにすることです。 ただし、 $ L\ge R $ のとき半開区間 $ [L,R) $ は空集合を表し、空集合は任意の区間と交わらないとします。 目標を達成するために必要な最小の操作回数を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。

### Universal Cup 参加者へ この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。 ### Sample Explanation 1 $ 1 $ つ目のテストケースについて、例えば - $ R_1 $ を $ 1 $ 減らす - $ L_3 $ を $ 1 $ 増やす と操作をすると、 $ 3 $ つの区間は $ [1,3),[3,7),[7,7) $ となり、これらは互いに交わりません。 $ 2 $ 回未満の操作で目標を達成することは不可能であることが示せるため、 $ 1 $ つ目のテストケースに対する答えは $ 2 $ です。 ### Constraints - $ 1 \le T \le 10^5 $ - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \le L_i\lt R_i \le 10^9 $ - $ 1 $ つの入力ファイルに含まれる $ N $ の総和は $ 2\times 10^5 $ 以下 - 入力は全て整数