시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 74 30 25 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을 넘지 않는 정수입니다) 가 공백을 두고 차례로 주어집니다.

출력

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

예제 입력 1

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

예제 출력 1

2
1
3
W3sicHJvYmxlbV9pZCI6IjczNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhYTlcdWFjZjVcdWMxOGNcdWM1ZDAgblx1YWMxY1x1Yzc1OCBcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViYjM0XHVhYzhjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWI5YzlcdWIzMDBcdWI0ZTRcdWM3NDAgXHVhZTMwXHVhY2M0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCZuYnNwO1x1ZDU1OFx1YjA5OCBcdWQ1NThcdWIwOTggXHVhYzAwXHVhY2Y1IFx1Y2M5OFx1YjlhYyBcdWFjZmNcdWM4MTVcdWM3NDQgXHVhYzcwXHVjZTU4XHVhYzhjIFx1YjQyOVx1YjJjOFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhYzAxIFx1YjljOVx1YjMwMFx1Yjk3YyBcdWNjOThcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWFlMzBcdWFjYzRcdWI5N2MgXHVjOTAwXHViZTQ0XHVjMmRjXHVkMGE0XHViMjk0IFx1YzJkY1x1YWMwNCwgXHVjOTg5Jm5ic3A7XHVhZTMwXHVhY2M0XHVjNzU4IFx1Yzc5MVx1YjNkOSBcdWM5MDBcdWJlNDQgXHVjMmRjXHVhYzA0KHNldHVwIHRpbWUpIFx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTY5XHViMmM4XHViMmU0LiBcdWM3NzQgXHVjNzkxXHViM2Q5IFx1YzkwMFx1YmU0NCBcdWMyZGNcdWFjMDRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJkODBcdWM1ZWNcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjY2FiIFx1YjljOVx1YjMwMFx1Yjk3YyBcdWFjMDBcdWFjZjVcdWQ1NjAgXHViNTRjIFx1YjRkY1x1YjI5NCBcdWM3OTFcdWIzZDkgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNFx1Yzc0MCAxXHViZDg0XHVjNzg1XHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFlMzhcdWM3NzQgbFx1YWNmYyBcdWJiMzRcdWFjOGMgd1x1Yzc3OCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVhYzAwXHVhY2Y1XHVkNTVjIFx1YzljMVx1ZDZjNCwgXHViMmU0XHVjNzRjIFx1YWMwMFx1YWNmNVx1ZDU2MCBcdWI5YzlcdWIzMDBcdWM3NTggXHVhZTM4XHVjNzc0IGwmIzM5O1x1YWNmYyBcdWJiMzRcdWFjOGMgdyYjMzk7XHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBsICZsZTsgbCYjMzk7IGFuZCB3ICZsZTsgdyYjMzk7IFx1Yzc3NFx1Yjc3Y1x1YmE3NCBcdWM3OTFcdWIzZDkgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0ZTRcdWM5YzAgXHVjNTRhXHVjMmI1XHViMmM4XHViMmU0LiBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0IFx1YWUzMFx1YWNjNFx1YWMwMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHViM2M0XHVhZDZjXHViOTdjIFx1YmMxNFx1YWZiOFx1YzViNFx1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIDFcdWJkODRcdWM3NTggXHVjNzkxXHViM2Q5IFx1YzkwMFx1YmU0NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTY5XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPm5cdWFjMWNcdWM3NTggXHViMDk4XHViYjM0IFx1YjljOVx1YjMwMFx1YjRlNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViYjM0XHVhYzhjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWI5YzlcdWIzMDBcdWI0ZTRcdWM3NDQgXHViYWE4XHViNDUwIFx1YWMwMFx1YWNmNVx1ZDU2MCBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWM3OTFcdWIzZDkgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWM1N2MgXHVkNTY5XHViMmM4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoNCw5KSwgKDUsMiksICgyLDEpLCAoMyw1KSwgKDEsNCkgXHVjNzU4IDVcdWFjMWMmbmJzcDtcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwXHViOTdjIFx1YWMwMFx1YWNmNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTc0IFx1YmQwNVx1YzJkY1x1YjJlNC4gXHViOWNjXHVjNTdkJm5ic3A7KDEsNCksICgzLDUpLCAoNCw5KSwgKDIsMSksICg1LDIpIFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVhYzAwXHVhY2Y1XHVkNTVjXHViMmU0XHViYTc0IFx1Y2QxZCAyXHViZDg0XHVjNzU4IFx1Yzc5MVx1YjNkOSBcdWM5MDBcdWJlNDQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YWNhMFx1YWNlMCwgXHVjNzc0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWNkNWNcdWMxOGNcdWM3NzRcdWJiYzBcdWI4NWMgXHViMmY1XHVjNzQwIDJcdWFjMDAgXHViNDE4XHVhY2EwXHVjOWMwXHVjNjk0PzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWIyOTQgXHViNDUwJm5ic3A7XHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMDk4XHViYjM0IFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFjMWNcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyA1MDAwKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwICZuYnNwO2w8c3ViPjE8XC9zdWI+LCB3PHN1Yj4xPFwvc3ViPiwmbmJzcDtsPHN1Yj4yPFwvc3ViPiwgdzxzdWI+MjxcL3N1Yj4sIC4uLiAsbDxzdWI+bjxcL3N1Yj4sIHc8c3ViPm48XC9zdWI+Jm5ic3A7Jm5ic3A7KFx1YWMwMSBcdWI5YzlcdWIzMDBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YmIzNFx1YWM4Y1x1Yjk3YyBcdWI3M2JcdWQ1NThcdWFjZTAsIDEwMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzg1XHViMmM4XHViMmU0KSBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YjQ1MFx1YWNlMCBcdWNjMjhcdWI4NDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViY2M0XHViODVjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjNzkxXHViM2Q5IFx1YzkwMFx1YmU0NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjZDljXHViODI1XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjczNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXb29kZW4gU3RpY2tzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIHBpbGUgb2YgbiB3b29kZW4gc3RpY2tzLiBUaGUgbGVuZ3RoIGFuZCB3ZWlnaHQgb2YgZWFjaCBzdGljayBhcmUga25vd24gaW4gYWR2YW5jZS4gVGhlIHN0aWNrcyBhcmUgdG8gYmUgcHJvY2Vzc2VkIGJ5IGEgd29vZHdvcmtpbmcgbWFjaGluZSBpbiBvbmUgYnkgb25lIGZhc2hpb24uIEl0IG5lZWRzIHNvbWUgdGltZSwgY2FsbGVkIHNldHVwIHRpbWUsIGZvciB0aGUgbWFjaGluZSB0byBwcmVwYXJlIHByb2Nlc3NpbmcgYSBzdGljay4gVGhlIHNldHVwIHRpbWVzIGFyZSBhc3NvY2lhdGVkIHdpdGggY2xlYW5pbmcgb3BlcmF0aW9ucyBhbmQgY2hhbmdpbmcgdG9vbHMgYW5kIHNoYXBlcyBpbiB0aGUgbWFjaGluZS4gVGhlIHNldHVwIHRpbWVzIG9mIHRoZSB3b29kd29ya2luZyBtYWNoaW5lIGFyZSBnaXZlbiBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48b2wgc3R5bGU9XCJsaXN0LXN0eWxlLXR5cGU6bG93ZXItYWxwaGFcIj5cclxuXHQ8bGk+VGhlIHNldHVwIHRpbWUgZm9yIHRoZSBmaXJzdCB3b29kZW4gc3RpY2sgaXMgMSBtaW51dGUuPFwvbGk+XHJcblx0PGxpPlJpZ2h0IGFmdGVyIHByb2Nlc3NpbmcgYSBzdGljayBvZiBsZW5ndGggbCBhbmQgd2VpZ2h0IHcgLCB0aGUgbWFjaGluZSB3aWxsIG5lZWQgbm8gc2V0dXAgdGltZSBmb3IgYSBzdGljayBvZiBsZW5ndGggbCYjMzk7IGFuZCB3ZWlnaHQgdyYjMzk7IGlmIGwgJmxlOyBsJiMzOTsgYW5kIHcgJmxlOyB3JiMzOTsuIE90aGVyd2lzZSwgaXQgd2lsbCBuZWVkIDEgbWludXRlIGZvciBzZXR1cC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Zb3UgYXJlIHRvIGZpbmQgdGhlIG1pbmltdW0gc2V0dXAgdGltZSB0byBwcm9jZXNzIGEgZ2l2ZW4gcGlsZSBvZiBuIHdvb2RlbiBzdGlja3MuIEZvciBleGFtcGxlLCBpZiB5b3UgaGF2ZSBmaXZlIHN0aWNrcyB3aG9zZSBwYWlycyBvZiBsZW5ndGggYW5kIHdlaWdodCBhcmUgKDQsOSkgLCAoNSwyKSwgKDIsMSkgLCAoMyw1KSAsIGFuZCAoMSw0KSAsIHRoZW4gdGhlIG1pbmltdW0gc2V0dXAgdGltZSBzaG91bGQgYmUgMiBtaW51dGVzIHNpbmNlIHRoZXJlIGlzIGEgc2VxdWVuY2Ugb2YgcGFpcnMgKDEsNCkgLCAoMyw1KSAsICg0LDkpICwgKDIsMSkgLCAoNSwyKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyAoVCkgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHR3byBsaW5lczogVGhlIGZpcnN0IGxpbmUgaGFzIGFuIGludGVnZXIgbiAsIDEgJmxlOyBuICZsZTsgNTAwMCAsIHRoYXQgcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIHdvb2RlbiBzdGlja3MgaW4gdGhlIHRlc3QgY2FzZSwgYW5kIHRoZSBzZWNvbmQgbGluZSBjb250YWlucyAybiBwb3NpdGl2ZSBpbnRlZ2VycyBsPHN1Yj4xPFwvc3ViPiwgdzxzdWI+MTxcL3N1Yj4sJm5ic3A7bDxzdWI+MjxcL3N1Yj4sIHc8c3ViPjI8XC9zdWI+LCAuLi4gLGw8c3ViPm48XC9zdWI+LCB3PHN1Yj5uPFwvc3ViPiwgZWFjaCBvZiBtYWduaXR1ZGUgYXQgbW9zdCAxMDAwMCAsIHdoZXJlIGw8c3ViPmk8XC9zdWI+IGFuZCB3PHN1Yj5pPFwvc3ViPiBhcmUgdGhlIGxlbmd0aCBhbmQgd2VpZ2h0IG9mIHRoZSBpIHRoIHdvb2RlbiBzdGljaywgcmVzcGVjdGl2ZWx5LiBUaGUgMm4gaW50ZWdlcnMgYXJlIGRlbGltaXRlZCBieSBvbmUgb3IgbW9yZSBzcGFjZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbWluaW11bSBzZXR1cCB0aW1lIGluIG1pbnV0ZXMsIG9uZSBwZXIgbGluZS48XC9wPlxyXG5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d