B. Many Tasks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Berta has a list of $$$n$$$ tasks. The $$$i$$$-th task requires $$$t_i$$$ seconds to be completed. Additionally, each task has a deadline $$$p_i$$$: the $$$i$$$-th task must be completed before more than $$$p_i + t_i$$$ seconds have passed since the start (therefore, it must be started at second $$$p_i$$$ or earlier).

Berta wants to perform the tasks strictly in the order they are written in her list, being able to skip some of them.

Help Berta determine the maximum number of tasks from her list that she can complete.

Input

The first line contains an integer $$$T$$$, the number of cases to process.

Each case begins with a line containing an integer $$$n$$$, the number of tasks. This is followed by $$$n$$$ lines, the $$$i$$$-th of which contains the two integers $$$t_i$$$ and $$$p_i$$$.

Output

For each case, print a line with the maximum number of tasks that can be completed.

Scoring
  1. (39 points) $$$t_i \leq n$$$, $$$p_i \leq n$$$ and the sum of $$$n^3$$$ over all cases is at most $$$10^6$$$.
  2. (15 points) All values of $$$p_i + t_i$$$ are equal: $$$p_1 + t_1 = p_2 + t_2 = \ldots = p_n + t_n$$$.
  3. (16 points) All values of $$$p_i$$$ are equal: $$$p_1 = p_2 = \ldots = p_n$$$.
  4. (30 points) No additional restrictions.
Example
Input
3
5
2 0
1 1
1 1
2 2
3 4
2
10000 100000000
1 9999
10
8 25
5 12
7 10
11 28
3 18
6 32
10 45
5 34
7 28
6 42
Output
4
1
7
Note
  • $$$1 \leq T \leq 10^3$$$.
  • $$$1 \leq n \leq 10^3$$$. The sum of $$$n^2$$$ over all cases is at most $$$10^6$$$.
  • $$$1 \leq t_i \leq 10^6$$$ for all $$$i = 1, \ldots, n$$$.
  • $$$0 \leq p_i \leq 10^9$$$ for all $$$i = 1, \ldots, n$$$.