33058번 - Job Completion 다국어

문제

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

What is the maximum number of jobs you can complete? Time starts at 0ドル,ドル 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 $T,ドル the number of independent test cases (1ドル\le T\le 10$). Each test case is formatted as follows.

The first line contains $N$.

Each of the next $N$ lines contains two integers $s_i$ and $t_i$. Row $i+1$ has the details for the $i$th job.

It is guaranteed that the sum of $N$ over all test cases does not exceed 3ドル\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 2ドル$ or later, so it is too late to start the other job, which must be started at time 1ドル$ or earlier.

For the second test case, you can start the second job at time 0ドル$ and finish at time 2ドル,ドル then start the first job at time 2ドル$ and finish at time 5ドル$.