Job Completion

문제

Bessie the cow has $NN$ ($1\le N\le 2\cdot {10}^{5}1\backslash le\; N\backslash le\; 2\backslash cdot\; 10^5$) jobs for you to potentially complete. The $ii$-th one, if you choose to complete it, must be started at or before time $s_{i}s\_i$ and takes $t_{i}t\_i$ time to complete ($0\le s_i\le {10}^{18},1\le t_i\le {10}^{18}0\backslash le\; s\_i\backslash le\; 10^\{18\},\; 1\backslash le\; t\_i\backslash le\; 10^\{18\}$).

What is the maximum number of jobs you can complete? Time starts at $00$, and once you start a job you must work on it until it is complete, without starting any other jobs in the meantime.

입력

The first line contains $TT$, the number of independent test cases ($1\le T\le 101\backslash le\; T\backslash le\; 10$). Each test case is formatted as follows.

The first line contains $NN$.

Each of the next $NN$ lines contains two integers $s_{i}s\_i$ and $t_{i}t\_i$. Row $i+1i+1$ has the details for the $ii$th job.

It is guaranteed that the sum of $NN$ over all test cases does not exceed $3\cdot {10}^{5}3\backslash cdot\; 10^5$.

출력

For each test case, the maximum number of jobs you can complete, on a new line.

힌트

For the first test case, you can only complete one of the jobs. After completing one job, it will then be time $22$ or later, so it is too late to start the other job, which must be started at time $11$ or earlier.

For the second test case, you can start the second job at time $00$ and finish at time $22$, then start the first job at time $22$ and finish at time $55$.

3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 2

1
2
2