시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 333 120 94 37.450%

문제

목공소에 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
W3sicHJvYmxlbV9pZCI6IjczNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhYTlcdWFjZjVcdWMxOGNcdWM1ZDAgblx1YWMxY1x1Yzc1OCBcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViYjM0XHVhYzhjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWI5YzlcdWIzMDBcdWI0ZTRcdWM3NDAgXHVhZTMwXHVhY2M0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCZuYnNwO1x1ZDU1OFx1YjA5OCBcdWQ1NThcdWIwOTggXHVhYzAwXHVhY2Y1IFx1Y2M5OFx1YjlhYyBcdWFjZmNcdWM4MTVcdWM3NDQgXHVhYzcwXHVjZTU4XHVhYzhjIFx1YjQyOVx1YjJjOFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjMDEgXHViOWM5XHViMzAwXHViOTdjIFx1Y2M5OFx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YWUzMFx1YWNjNFx1Yjk3YyBcdWM5MDBcdWJlNDRcdWMyZGNcdWQwYTRcdWIyOTQgXHVjMmRjXHVhYzA0LCBcdWM5ODkmbmJzcDtcdWFlMzBcdWFjYzRcdWM3NTggXHVjNzkxXHViM2Q5IFx1YzkwMFx1YmU0NCBcdWMyZGNcdWFjMDQoc2V0dXAgdGltZSkgXHVjNzc0XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWM3OTFcdWIzZDkgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YmQ4MFx1YzVlY1x1YjQyOVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWNjYWIgXHViOWM5XHViMzAwXHViOTdjIFx1YWMwMFx1YWNmNVx1ZDU2MCBcdWI1NGMgXHViNGRjXHViMjk0IFx1Yzc5MVx1YjNkOSBcdWM5MDBcdWJlNDQgXHVjMmRjXHVhYzA0XHVjNzQwIDFcdWJkODRcdWM3ODVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWUzOFx1Yzc3NCBsXHVhY2ZjIFx1YmIzNFx1YWM4YyB3XHVjNzc4IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWFjMDBcdWFjZjVcdWQ1NWMgXHVjOWMxXHVkNmM0LCBcdWIyZTRcdWM3NGMgXHVhYzAwXHVhY2Y1XHVkNTYwIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzQgbCYjMzk7XHVhY2ZjIFx1YmIzNFx1YWM4YyB3JiMzOTtcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIGwgJmxlOyBsJiMzOTsgYW5kIHcgJmxlOyB3JiMzOTsgXHVjNzc0XHViNzdjXHViYTc0IFx1Yzc5MVx1YjNkOSBcdWM5MDBcdWJlNDQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjRlNFx1YzljMCBcdWM1NGFcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQgXHVhZTMwXHVhY2M0XHVhYzAwIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWIzYzRcdWFkNmNcdWI5N2MgXHViYzE0XHVhZmI4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgMVx1YmQ4NFx1Yzc1OCBcdWM3OTFcdWIzZDkgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+blx1YWMxY1x1Yzc1OCBcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YzY0MCBcdWJiMzRcdWFjOGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YjljOVx1YjMwMFx1YjRlNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhYzAwXHVhY2Y1XHVkNTYwIFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1Yzc5MVx1YjNkOSBcdWM5MDBcdWJlNDQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YzU3YyBcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICg0LDkpLCAoNSwyKSwgKDIsMSksICgzLDUpLCAoMSw0KSBcdWM3NTggNVx1YWMxYyZuYnNwO1x1YjA5OFx1YmIzNCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVhYzAwXHVhY2Y1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NzQgXHViZDA1XHVjMmRjXHViMmU0LiBcdWI5Y2NcdWM1N2QmbmJzcDsoMSw0KSwgKDMsNSksICg0LDkpLCAoMiwxKSwgKDUsMikgXHVjNzU4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjMDBcdWFjZjVcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjZDFkIDJcdWJkODRcdWM3NTggXHVjNzkxXHViM2Q5IFx1YzkwMFx1YmU0NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHVhY2EwXHVhY2UwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1Yzc3NFx1YmJjMFx1Yjg1YyBcdWIyZjVcdWM3NDAgMlx1YWMwMCBcdWI0MThcdWFjYTBcdWM5YzBcdWM2OTQ/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWI0NTAmbmJzcDtcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwXHVjNzU4IFx1YWMxY1x1YzIxOCBuICgxICZsZTsgbiAmbGU7IDUwMDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgJm5ic3A7bDxzdWI+MTxcL3N1Yj4sIHc8c3ViPjE8XC9zdWI+LCZuYnNwO2w8c3ViPjI8XC9zdWI+LCB3PHN1Yj4yPFwvc3ViPiwgLi4uICxsPHN1Yj5uPFwvc3ViPiwgdzxzdWI+bjxcL3N1Yj4mbmJzcDsmbmJzcDsoXHVhYzAxIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViYjM0XHVhYzhjXHViOTdjIFx1YjczYlx1ZDU1OFx1YWNlMCwgMTAwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM4MTVcdWMyMThcdWM3ODVcdWIyYzhcdWIyZTQpIFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWJjYzRcdWI4NWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM3OTFcdWIzZDkgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3MzQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV29vZGVuIFN0aWNrcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgaXMgYSBwaWxlIG9mIG4gd29vZGVuIHN0aWNrcy4gVGhlIGxlbmd0aCBhbmQgd2VpZ2h0IG9mIGVhY2ggc3RpY2sgYXJlIGtub3duIGluIGFkdmFuY2UuIFRoZSBzdGlja3MgYXJlIHRvIGJlIHByb2Nlc3NlZCBieSBhIHdvb2R3b3JraW5nIG1hY2hpbmUgaW4gb25lIGJ5IG9uZSBmYXNoaW9uLiBJdCBuZWVkcyBzb21lIHRpbWUsIGNhbGxlZCBzZXR1cCB0aW1lLCBmb3IgdGhlIG1hY2hpbmUgdG8gcHJlcGFyZSBwcm9jZXNzaW5nIGEgc3RpY2suIFRoZSBzZXR1cCB0aW1lcyBhcmUgYXNzb2NpYXRlZCB3aXRoIGNsZWFuaW5nIG9wZXJhdGlvbnMgYW5kIGNoYW5naW5nIHRvb2xzIGFuZCBzaGFwZXMgaW4gdGhlIG1hY2hpbmUuIFRoZSBzZXR1cCB0aW1lcyBvZiB0aGUgd29vZHdvcmtpbmcgbWFjaGluZSBhcmUgZ2l2ZW4gYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPG9sIHN0eWxlPVwibGlzdC1zdHlsZS10eXBlOmxvd2VyLWFscGhhXCI+XHJcblx0PGxpPlRoZSBzZXR1cCB0aW1lIGZvciB0aGUgZmlyc3Qgd29vZGVuIHN0aWNrIGlzIDEgbWludXRlLjxcL2xpPlxyXG5cdDxsaT5SaWdodCBhZnRlciBwcm9jZXNzaW5nIGEgc3RpY2sgb2YgbGVuZ3RoIGwgYW5kIHdlaWdodCB3ICwgdGhlIG1hY2hpbmUgd2lsbCBuZWVkIG5vIHNldHVwIHRpbWUgZm9yIGEgc3RpY2sgb2YgbGVuZ3RoIGwmIzM5OyBhbmQgd2VpZ2h0IHcmIzM5OyBpZiBsICZsZTsgbCYjMzk7IGFuZCB3ICZsZTsgdyYjMzk7LiBPdGhlcndpc2UsIGl0IHdpbGwgbmVlZCAxIG1pbnV0ZSBmb3Igc2V0dXAuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+WW91IGFyZSB0byBmaW5kIHRoZSBtaW5pbXVtIHNldHVwIHRpbWUgdG8gcHJvY2VzcyBhIGdpdmVuIHBpbGUgb2YgbiB3b29kZW4gc3RpY2tzLiBGb3IgZXhhbXBsZSwgaWYgeW91IGhhdmUgZml2ZSBzdGlja3Mgd2hvc2UgcGFpcnMgb2YgbGVuZ3RoIGFuZCB3ZWlnaHQgYXJlICg0LDkpICwgKDUsMiksICgyLDEpICwgKDMsNSkgLCBhbmQgKDEsNCkgLCB0aGVuIHRoZSBtaW5pbXVtIHNldHVwIHRpbWUgc2hvdWxkIGJlIDIgbWludXRlcyBzaW5jZSB0aGVyZSBpcyBhIHNlcXVlbmNlIG9mIHBhaXJzICgxLDQpICwgKDMsNSkgLCAoNCw5KSAsICgyLDEpICwgKDUsMikuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgKFQpIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0d28gbGluZXM6IFRoZSBmaXJzdCBsaW5lIGhhcyBhbiBpbnRlZ2VyIG4gLCAxICZsZTsgbiAmbGU7IDUwMDAgLCB0aGF0IHJlcHJlc2VudHMgdGhlIG51bWJlciBvZiB3b29kZW4gc3RpY2tzIGluIHRoZSB0ZXN0IGNhc2UsIGFuZCB0aGUgc2Vjb25kIGxpbmUgY29udGFpbnMgMm4gcG9zaXRpdmUgaW50ZWdlcnMgbDxzdWI+MTxcL3N1Yj4sIHc8c3ViPjE8XC9zdWI+LCZuYnNwO2w8c3ViPjI8XC9zdWI+LCB3PHN1Yj4yPFwvc3ViPiwgLi4uICxsPHN1Yj5uPFwvc3ViPiwgdzxzdWI+bjxcL3N1Yj4sIGVhY2ggb2YgbWFnbml0dWRlIGF0IG1vc3QgMTAwMDAgLCB3aGVyZSBsPHN1Yj5pPFwvc3ViPiBhbmQgdzxzdWI+aTxcL3N1Yj4gYXJlIHRoZSBsZW5ndGggYW5kIHdlaWdodCBvZiB0aGUgaSB0aCB3b29kZW4gc3RpY2ssIHJlc3BlY3RpdmVseS4gVGhlIDJuIGludGVnZXJzIGFyZSBkZWxpbWl0ZWQgYnkgb25lIG9yIG1vcmUgc3BhY2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIG1pbmltdW0gc2V0dXAgdGltZSBpbiBtaW51dGVzLCBvbmUgcGVyIGxpbmUuPFwvcD5cclxuXHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d