시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 118 5 5 20.833%

문제

알고스팟 대학교에는 서로를 정말 싫어하는 교수 두 명이 있다. 이 대학교에서는 교수의 이름을 숫자로 부른다. 서로 싫어하는 두 교수의 번호는 1과 2이다.

알고스팟 대학교에는 총 n명의 교수가 있고, 수업은 매일 매일 같은 시간에 진행된다. 각 교수가 맡은 수업은 하나이다. 모든 수업의 시작 시간과 종료 시간은 정해져있다. 또, 수업을 조금 더 늦게 끝내거나, 일찍 시작하는 것은 불가능하다. 학교에서 정한 수업 이외의 수업은 할 수 없다.

아직 학교는 수업의 강의실을 정해놓지 않았다. 시간이 겹치는 수업은 같은 강의실에 배정할 수 없다. 하지만, 끝 시간과 시작 시간이 같은 두 수업은 같은 강의실에 배정할 수 있다. 모든 수업에 강의실을 배정할 때, 필요한 강의실의 최소 개수를 구하는 프로그램을 작성하시오. 1번 교수와 2번 교수는 서로를 매우 싫어하기 때문에, 같은 강의실에서 수업을 진행하지 않는다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 250) 각 테스트 케이스의 첫째 줄에는 교수의 수 n (2 ≤ n ≤ 105)이 주어진다. 다음 n개 줄에는 i번 교수가 맡은 수업의 시작 시간 starti와 끝 시간 endi가 주어진다. (0 ≤ starti < endi ≤ 109) 입력의 크기는 50MB를 넘지 않는다.

출력

모든 수업에 강의실을 배정하는데 필요한 강의실의 최소 개수를 출력한다.

예제 입력 1

4
2
0 10
10 20
3
0 10
10 20
10 20
5
4 14
3 13
2 12
1 11
0 10
4
0 10
10 20
20 30
30 40

예제 출력 1

2
2
5
2
W3sicHJvYmxlbV9pZCI6Ijc4ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0NTAgXHVhZDUwXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWFjZTBcdWMyYTRcdWQzMWYgXHViMzAwXHVkNTU5XHVhZDUwXHVjNWQwXHViMjk0IFx1YzExY1x1Yjg1Y1x1Yjk3YyBcdWM4MTVcdWI5ZDAgXHVjMmViXHVjNWI0XHVkNTU4XHViMjk0IFx1YWQ1MFx1YzIxOCBcdWI0NTAgXHViYTg1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjMwMFx1ZDU1OVx1YWQ1MFx1YzVkMFx1YzExY1x1YjI5NCBcdWFkNTBcdWMyMThcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQ0IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWJkODBcdWI5NzhcdWIyZTQuIFx1YzExY1x1Yjg1YyBcdWMyZWJcdWM1YjRcdWQ1NThcdWIyOTQgXHViNDUwIFx1YWQ1MFx1YzIxOFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YWNmYyAyXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NGNcdWFjZTBcdWMyYTRcdWQzMWYgXHViMzAwXHVkNTU5XHVhZDUwXHVjNWQwXHViMjk0IFx1Y2QxZCBuXHViYTg1XHVjNzU4IFx1YWQ1MFx1YzIxOFx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YzIxOFx1YzVjNVx1Yzc0MCBcdWI5ZTRcdWM3N2MgXHViOWU0XHVjNzdjIFx1YWMxOVx1Yzc0MCBcdWMyZGNcdWFjMDRcdWM1ZDAgXHVjOWM0XHVkNTg5XHViNDFjXHViMmU0LiZuYnNwO1x1YWMwMSBcdWFkNTBcdWMyMThcdWFjMDAgXHViOWUxXHVjNzQwIFx1YzIxOFx1YzVjNVx1Yzc0MCBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMyMThcdWM1YzVcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzJkY1x1YWMwNFx1YWNmYyBcdWM4ODVcdWI4Y2MgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzgxNVx1ZDU3NFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHViNjEwLCZuYnNwO1x1YzIxOFx1YzVjNVx1Yzc0NCBcdWM4NzBcdWFlMDggXHViMzU0IFx1YjJhNlx1YWM4YyBcdWIwNWRcdWIwYjRcdWFjNzBcdWIwOTgsIFx1Yzc3Y1x1Y2MwZCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC4gXHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjIFx1YzgxNVx1ZDU1YyBcdWMyMThcdWM1YzUgXHVjNzc0XHVjNjc4XHVjNzU4IFx1YzIxOFx1YzVjNVx1Yzc0MCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHVjOWMxIFx1ZDU1OVx1YWQ1MFx1YjI5NCBcdWMyMThcdWM1YzVcdWM3NTggXHVhYzE1XHVjNzU4XHVjMmU0XHVjNzQ0IFx1YzgxNVx1ZDU3NFx1YjE5M1x1YzljMCBcdWM1NGFcdWM1NThcdWIyZTQuIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjYjlcdWNlNThcdWIyOTQgXHVjMjE4XHVjNWM1XHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWFjMTVcdWM3NThcdWMyZTRcdWM1ZDAgXHViYzMwXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViMDVkIFx1YzJkY1x1YWMwNFx1YWNmYyBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWI0NTAgXHVjMjE4XHVjNWM1XHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWFjMTVcdWM3NThcdWMyZTRcdWM1ZDAgXHViYzMwXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMyMThcdWM1YzVcdWM1ZDAgXHVhYzE1XHVjNzU4XHVjMmU0XHVjNzQ0IFx1YmMzMFx1YzgxNVx1ZDU2MCBcdWI1NGMsIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFjMTVcdWM3NThcdWMyZTRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gMVx1YmM4OCBcdWFkNTBcdWMyMThcdWM2NDAgMlx1YmM4OCBcdWFkNTBcdWMyMThcdWIyOTQgXHVjMTFjXHViODVjXHViOTdjIFx1YjllNFx1YzZiMCBcdWMyZWJcdWM1YjRcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWFjMTlcdWM3NDAgXHVhYzE1XHVjNzU4XHVjMmU0XHVjNWQwXHVjMTFjIFx1YzIxOFx1YzVjNVx1Yzc0NCBcdWM5YzRcdWQ1ODlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCB0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKHQgJmxlOyAyNTApIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZDUwXHVjMjE4XHVjNzU4IFx1YzIxOCBuICgyICZsZTsgbiAmbGU7IDEwPHN1cD41PFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OCBcdWFkNTBcdWMyMThcdWFjMDAgXHViOWUxXHVjNzQwIFx1YzIxOFx1YzVjNVx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0IHN0YXJ0PHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWIwNWQgXHVjMmRjXHVhYzA0IGVuZDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IHN0YXJ0PHN1Yj5pPFwvc3ViPiAmbHQ7IGVuZDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgNTBNQlx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmFhOFx1YjRlMCBcdWMyMThcdWM1YzVcdWM1ZDAgXHVhYzE1XHVjNzU4XHVjMmU0XHVjNzQ0IFx1YmMzMFx1YzgxNVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhYzE1XHVjNzU4XHVjMmU0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc4ODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUd28gcHJvZmVzc29ycyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIHR3byBwcm9mZXNzb3JzIGF0IHRoZSBncmVhdCBBY2FkZW15IG9mIFggdGhhdCByZWFsbHkgZG8gbm90IGdldCBhbG9uZyB3aXRoIGVhY2ggb3RoZXIuIEluIG9yZGVyIG5vdCB0byByZXZlYWwgdGhlaXIgbmFtZXMsIHdlIHdpbGwgY2FsbCB0aGVtIDEgYW5kIDIuIFRoZSBBY2FkZW15IGVtcGxveXMgZXhhY3RseSBuIHByb2Zlc3NvcnM7IGVhY2ggb2YgdGhlbSBoYXMgdG8gZ2l2ZSBleGFjdGx5IG9uZSBsZWN0dXJlLiBBcyB0aGVpciBzY2hlZHVsZXMgYXJlIHJhdGhlciB0aWdodCAodGhleSBhcmUgcHJvZmVzc29ycywgcmVtZW1iZXI/KSwgdGhlIHN0YXJ0aW5nIGFuZCB0aGUgZW5kaW5nIHRpbWUgb2YgZWFjaCBsZWN0dXJlIGlzIGFscmVhZHkgeGVkLiBIb3dldmVyLCBpdCBpcyBub3QgeWV0IGZpIHhlZCB3aGVyZSBlYWNoIGxlY3R1cmUgd2lsbCB0YWtlIHBsYWNlLiBPYnZpb3VzbHksIGl0IGlzIGltcG9zc2libGUgdG8gc2NoZWR1bGUgdHdvIGxlY3R1cmVzIGluIHRoZSBzYW1lIHJvb20gaWYgdGhlaXIgZHVyYXRpb25zIG92ZXJsYXA7IG9uIHRoZSBvdGhlciBoYW5kLCBpdCBpcyBwb3NzaWJsZSBpZiBvbmUgb2YgdGhlbSBzdGFydHMgZXhhY3RseSBhdCB0aGUgc2FtZSB0aW1lIHRoYXQgdGhlIG90aGVyIG9uZSBlbmRzLiBZb3VyIHRhc2tzIGlzIHRvIG5kIHRoZSBtaW5pbWFsIG51bWJlciBvZiByb29tcyBhbGxvd2luZyB0byBhcnJhbmdlIGFsbCB0aGUgbGVjdHVyZXMuIEJ1dCBrbm93IHRoYXQgcHJvZmVzc29ycyAxIGFuZCAyIGhhdGUgZWFjaCBvdGhlciBzbyBtdWNoIHRoYXQgdGhleSB3aWxsIG5ldmVyIGdpdmUgdGhlaXIgbGVjdHVyZXMgaW4gdGhlIHNhbWUgcm9vbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIFRoZSByc3QgbGluZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdCAodCAmbGU7IDI1MCkuIEVhY2ggdGVzdCBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIHByb2Zlc3NvcnMgbiAoMiAmbGU7IG4gJmxlOyAxMDxzdXA+NTxcL3N1cD4pLiBOZXh0IG4gbGluZXMgZm9sbG93LCBpLXRoIG9mIHdoaWNoIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBzdGFydDxzdWI+aTxcL3N1Yj4gYW5kIGVuZDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBzdGFydDxzdWI+aTxcL3N1Yj4gJmx0OyBlbmQ8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgdGhlIHN0YXJ0aW5nIGFuZCB0aGUgZW5kaW5nIHRpbWUgb2YgdGhlIGxlY3R1cmUgdGhhdCB0aGUgaS10aCBwcm9mZXNzb3IgZ2l2ZXMsIHJlc3BlY3RpdmVseS4gVG90YWwgc2l6ZSBvZiB0aGUgaW5wdXQgd2lsbCBub3QgZXhjZWVkIDUwTUIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCB0aGUgbWluaW1hbCBudW1iZXIgb2Ygcm9vbXMgbmVjZXNzYXJ5IHRvIHNjaGVkdWxlIGFsbCB0aGUgbGVjdHVyZXMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==