beecrowd | 2073

# Cairo's Market

By XIV Maratona de Programação IME-USP, 2010 Brazil

Timelimit: 3

Your team is already making plans for a visit to Egypt. One of the places we want to know is the famous market of Cairo. To save time, you decided that will enter the door at the southwest corner of the market and out the door in the northeast corner. Moreover, you will always walk toward the exit, i.e., will only move to the north or east.

The market is well organized. The spans where tents can be placed have the same height and width. Each span is identified by a (x, y) coordinate that indicates the column and row of its market. From an aerial view you can see that all spans are arranged as a grid. The market tents were assembled only valid in spans (and strictly comply with the measures of the span). Being in a tent you can go to the tents that are strictly north, east and northeast.

Knowing the age of the sellers and the position of the tent where everyone works, determine the maximum number of items you can buy.

## Input

The input is composed of several instances. The first line of input contains an integer T indicating the number of instances.

The first line of each instance contains an integer N (1 ≤ N ≤ 100000), indicating the number of sellers in the market. Each of the next N lines contains two integers each, xi and yi (1 ≤ xi, yi ≤ 1000), indicating the coordinates of the tent in which the i-th seller works.

Sellers are listed in order of age, youngest to oldest. Two or more vendors can share the same tent. In this case you can trade (or fail to trade) with them in any order.

Go north means increasing the value of y and go east means increasing the value of x. All tents are within the market.

## Output

For each instance print a line containing a single integer, the maximum number of items you can buy.

 Sample Input Sample Output 5 1 1 1 2 1 1 1 2 2 2 1 1 1 3 1 1 1 2 2 1 4 1 1 1 2 2 1 2 2 1 2 1 2 3