시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 63 26 22 50.000%

문제

목공소에 n개의 나무 막대가 있고, 각 막대의 길이와 무게가 주어져 있습니다. 이 막대들은 기계를 이용해 하나 하나 가공 처리 과정을 거치게 됩니다. 이 때, 각 막대를 처리할 수 있도록 기계를 준비시키는 시간, 즉 기계의 작동 준비 시간(setup time) 이라는 것이 존재합니다. 이 작동 준비 시간은 다음과 같이 부여됩니다.

  1. 첫 막대를 가공할 때 드는 작동 준비 시간은 1분입니다.
  2. 길이 l과 무게 w인 막대를 가공한 직후, 다음 가공할 막대의 길이 l'과 무게 w'에 대하여 l ≤ l' and w ≤ w' 이라면 작동 준비 시간이 들지 않습니다. 그렇지 않다면 기계가 사용하는 도구를 바꾸어야 하기 때문에 1분의 작동 준비 시간이 필요합니다.

n개의 나무 막대들의 길이와 무게가 주어졌을 때, 이 막대들을 모두 가공할 때 필요한 최소한의 작동 준비 시간을 구해야 합니다. 예를 들어, (4,9), (5,2), (2,1), (3,5), (1,4) 의 5개 나무 막대를 가공해야 한다고 해 봅시다. 만약 (1,4), (3,5), (4,9), (2,1), (5,2) 의 순서대로 가공한다면 총 2분의 작동 준비 시간이 필요하겠고, 이 경우가 최소이므로 답은 2가 되겠지요?

입력

첫째 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 데이터는 두 줄에 걸쳐 주어집니다. 첫째 줄에는 나무 막대의 개수 n (1 ≤ n ≤ 5000) 이 주어지고, 다음 줄에  l1, w1, l2, w2, ... ,ln, wn  (각 막대의 길이와 무게를 뜻하고, 10000을 넘지 않는 정수입니다) 가 공백을 두고 차례로 주어집니다.

출력

각 테스트 케이스별로 필요한 최소 작동 준비 시간을 한 줄에 걸쳐 출력합니다.

예제 입력

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

예제 출력

2
1
3

힌트