Chiaki has `n` intervals and the `i`-th of them is [`l`_{i}, `r`_{i}]. She wants to delete some intervals so that there does not exist three intervals `a`, `b` and `c` such that `a` intersects with `b`, `b` intersects with `c` and `c` intersects with `a`.

Chiaki is interested in the minimum number of intervals which need to be deleted.

Note that interval `a` intersects with interval `b` if there exists a real number `x` such that `l`_{a} ≤ `x` ≤ `r`_{a} and `l`_{b} ≤ `x` ≤ `r`_{b}.

There are multiple test cases. The first line of input contains an integer `T`, indicating the number of test cases. For each test case:

The first line contains an integer `n` (1 ≤ `n` ≤ 50000) -- the number of intervals.

Each of the following `n` lines contains two integers `l`_{i} and `r`_{i} (1 ≤ `l`_{i} < `r`_{i} ≤ 10^{9}) denoting the `i`-th interval. Note that for every 1 ≤ `i` < `j` ≤ `n`, `l`_{i} ≠ `l`_{j} or `r`_{i} ≠ `r`_{j}.

It is guaranteed that the sum of all `n` does not exceed 500000.

提交代码