시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 254 65 50 25.381%

문제

어떠한 다이아몬드의 가치는 그 다이아몬드의 중량인 캐럿과 선명도에 의해서 결정됩니다. 즉, 작지만 선명한 다이아몬드가 크고 선명하지 않은 다이아몬드보다는 가치가 높습니다. 다이아몬드의 선명도는 0.0-10.0의 스캐일로 표현할 수 있는데, 0.0의 선명도는 완벽하게 선명한 다이아몬드를 나타내고 10.0은 가장 결함이 많은 다이아몬드를 나타냅니다.

N개의 다이아몬드의 중량 wi와 선명도 ci의 정보가 주어졌을때, 이 중에서 다이아몬드의 가치가 높아지는 부분열중 최장의 것의 길이를 구하세요. 예를들어 주어진 정보가 다음과 같다면

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

다이아몬드의 가치가 높아지는 부분열중 길이가 최장인것은 다음과 같습니다:

1.5 9.0
2.5 6.0
3.0 5.0
4.0 2.0

표에서 볼 수 있듯이, 가치가 높은 다이아몬드일수로 무게의 값은 크고 선명도의 값은 낮습니다.

입력

테스트 케이스의 갯수 T가 주어지고 (1≤T≤100) 각 테스트 케이스마다 다이아몬드의 정보의 갯수 N (1≤N≤200)이 주어집니다. 그리고 N개의 줄에 걸쳐서 다이아몬드의 무게와 선명도 wi, ci가 주어집니다 (0≤wi,ci≤100).

출력

각 테스트 케이스마다 다이아몬드의 가치가 높아지는 부분열중 최장의 것의 길이를 구하세요.

예제 입력

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

예제 출력

2
1
4

힌트