beecrowd | 2073

Cairo's Market

By XIV Maratona de Programação IME-USP, 2010 BR 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 Egyptians sellers have a peculiar rule. If you buy something from one of them, you can only buy again from another seller who is older. The punishment for breaking this rule is to lose a hand. Of course it can harm your team at the end of the ICPC. For this reason, you think best to follow local traditions. How it’s nothing elegant to give the same type of souvenir for all your friends, you've decided that in addition to following the rules of the market will buy at most one souvenir from each salesperson. This will help you have a good variety of gifts.

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

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