文理学院程序设计在线练习


Diamonds

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 27   Accepted Submission(s): 10
Problem Description

A diamond’s overall worth is determined by its mass in carats as well as its overall clarity. A large diamond with many imperfections is not worth as much as a smaller, flawless diamond. The overall clarity of a diamond can be described on a scale from 0.0–10.0 adopted by the American Gem Society, where 0.0 represents a flawless diamond and 10.0 represents an imperfect diamond.
Given a sequence of N diamonds, each with weight, wi, in carats and clarity, ci, on the scale described above, find the longest subsequence of diamonds for which the weight and clarity are both becoming strictly more favorable to a buyer.

For example,in the following sequence of diamonds,
wi  ci
1.5 9.0
2.0 2.0
2.5 6.0
3.0 5.0
4.0 2.0
10.0 5.5

the longest desirable subsequence is
1.5 9.0
2.5 6.0
3.0 5.0
4.0 2.0

because the weights strictly increase while the clarities strictly decrease.

Input

Input begins with a line with a single integer T, 1 ≤ T ≤ 100, indicating the number of test cases.
Each test case begins with a line with a single integer N, 1 ≤ N ≤ 200, indicating the number of diamonds. Next follow N lines with 2 real numbers wi and ci, 0.0 ≤ wi,ci ≤ 10.0, indicating the weight in carats and the clarity of diamond i, respectively.

Output

For each test case, output a single line with the length of the longest desirable subsequence of diamonds.

Sample Input
3
2
1.0 1.0
1.5 0.0
3
1.0 1.0
1.0 1.0
1.0 1.0
6
1.5 9.0
2.0 2.0
2.5 6.0
3.0 5.0
4.0 2.0
10.0 5.5
Sample Output
2
1
4