Domino

Time limit1sMemory limit128 MB

Summary

Topple one domino left or right and count how many fall in the longest chain reaction.

Level: Medium6 of 10
Topics: Dynamic programming, Binary search, Segment tree
Solved: No attempts yet

Problem

For Christmas, Jarek received a set of dominoes of different heights and stood them all upright in a single row.

If Jarek topples a domino of height $H$ at position $X$ to the right, every domino at positions $X+1, X+2, \dots, X+H$ falls to the right. Likewise, toppling a domino of height $H$ at position $X$ to the left makes every domino at positions $X-1, X-2, \dots, X-H$ fall to the left. Each domino that falls topples the following dominoes in the same direction (a chain reaction).

Given the position and height of every domino, find the maximum number of dominoes that fall when a single domino is toppled in either direction.

Input

The first line contains the number of test cases $Z$ ( $1 \le Z \le 10$ ).

The first line of each test case contains the number of dominoes $N$ ( $1 \le N \le 10^5$ ). Each of the next $N$ lines contains two integers $X$ and $H$ ( $1 \le X, H \le 10^9$ ), the position and height of a domino. The positions are given in increasing order.

Output

For each test case, print on its own line the maximum number of dominoes that can be toppled by knocking over a single domino.

Examples2

Example 1
Input
```
1
4
1 2
4 1
5 2
7 1
```
Expected output
```
3
```
Example 2
Input
```
1
6
1 1
2 1
3 1
4 1
5 1
6 1
```
Expected output
```
6
```