Universal Cup 参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

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 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 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 以下
• 入力は全て整数

入力例 1

4
3
1 4
3 7
6 7
2
1 1000000000
1 1000000000
2
1 2
2 3
4
20 25
3 22
3 23
3 24

出力例 1

2
999999999
0
43

1 つ目のテストケースについて、例えば

• R_1 を 1 減らす
• L_3 を 1 増やす

と操作をすると、3 つの区間は [1,3),[3,7),[7,7) となり、これらは互いに交わりません。
2 回未満の操作で目標を達成することは不可能であることが示せるため、1 つ目のテストケースに対する答えは 2 です。