시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 304 104 78 32.365%

문제

상근이는 올림픽을 매우 좋아하면서 싫어한다. 올림픽을 좋아하는 이유는 많은 스포츠 경기를 볼 수 있기 때문이고, 싫어하는 이유는 경기가 동시에 열리기 때문이다.

방금 올림픽이 열리는 장소에 도착을 했다. 하지만, 경기가 동시에 열리기 때문에, 상근이는 모든 경기를 실시간으로 볼 수 없다.

모든 경기의 시작 시간과 종료 시간, 그리고 날짜가 주어진다. 이때, 상근이가 볼 수 있는 경기의 최대 개수를 구하는 프로그램을 작성하시오. 상근이는 경기장에 시작 시간에 들어가며, 종료 시간에 나오게된다. 한 경기를 보던 중에 다른 경기를 보기 위해 경기장을 옮길 수 없다. 또, 경기장을 이동하는데 걸리는 시간은 없다. 마지막으로, 경기가 시작된 이후에는 경기장에 들어갈 수 없다.

입력

입력의 첫째 줄에는 테스트 케이스의 개수 n이 주어진다.

각 테스트 케이스의 첫째 줄에는 경기의 수  1 ≤ m ≤ 50000 이 주어진다. 다음 m개 줄에는 각 경기의 정보를 나타내는 세 정수 d, s, e가 주어진다. d는 경기의 날짜, s는 시작 시간, e는 종료 시간을 나타낸다. 시간은 hhmm형식으로 주어지며, 모든 경기는 시작한 날에 끝난다.

출력

각 테스트 케이스마다 "Scenario #i:"를 출력한다. 여기서 i는 테스트 케이스 번호이며 1부터 시작한다. 그 다음 줄에는 상근이가 참석할 수 있는 경기의 최대 개수를 출력한다. 문제에서도 설명했지만, 경기장을 이동하는데 걸리는 시간은 없다. 즉, 경기 A의 종료 시간이 B의 시작 시간과 같은 경우에 상근이는 A 이후에 바로 B로 이동할 수 있다. 각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력 1

2
10
1 1220 1340
2 1155 1220
2 1220 1340
3 1220 1240
1 1200 1320
2 1250 1310
2 1330 1550
3 1030 1130
3 1130 1300
3 1240 1330
3
1 0500 2200
1 0000 0700
1 2000 2359

예제 출력 1

Scenario #1:
7

Scenario #2:
2
W3sicHJvYmxlbV9pZCI6Ijc1MDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MmNcdWI5YmNcdWQ1M2QgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNjJjXHViOWJjXHVkNTNkXHVjNzQ0IFx1YjllNFx1YzZiMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWJhNzRcdWMxMWMgXHVjMmViXHVjNWI0XHVkNTVjXHViMmU0LiBcdWM2MmNcdWI5YmNcdWQ1M2RcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWI5Y2VcdWM3NDAgXHVjMmE0XHVkM2VjXHVjZTIwIFx1YWNiZFx1YWUzMFx1Yjk3YyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWFjZTAsIFx1YzJlYlx1YzViNFx1ZDU1OFx1YjI5NCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVhY2JkXHVhZTMwXHVhYzAwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM1ZjRcdWI5YWNcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMjlcdWFlMDggXHVjNjJjXHViOWJjXHVkNTNkXHVjNzc0IFx1YzVmNFx1YjlhY1x1YjI5NCBcdWM3YTVcdWMxOGNcdWM1ZDAgXHViM2M0XHVjYzI5XHVjNzQ0IFx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFjYmRcdWFlMzBcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YzVmNFx1YjlhY1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2JkXHVhZTMwXHViOTdjIFx1YzJlNFx1YzJkY1x1YWMwNFx1YzczY1x1Yjg1YyBcdWJjZmMgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1Yzg4NVx1YjhjYyBcdWMyZGNcdWFjMDQsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwYTBcdWM5ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWFlMzBcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWNiZFx1YWUzMFx1YzdhNVx1YzVkMCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwMFx1YmE3MCwgXHVjODg1XHViOGNjIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWIwOThcdWM2MjRcdWFjOGNcdWI0MWNcdWIyZTQuIFx1ZDU1YyBcdWFjYmRcdWFlMzBcdWI5N2MgXHViY2Y0XHViMzU4IFx1YzkxMVx1YzVkMCBcdWIyZTRcdWI5NzggXHVhY2JkXHVhZTMwXHViOTdjIFx1YmNmNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzQ0IFx1YzYyZVx1YWUzOCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI2MTAsIFx1YWNiZFx1YWUzMFx1YzdhNVx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWM1YzZcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YywgXHVhY2JkXHVhZTMwXHVhYzAwIFx1YzJkY1x1Yzc5MVx1YjQxYyBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YzIxOCAmbmJzcDsxICZsZTsgbSAmbGU7IDUwMDAwIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBkLCBzLCBlXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gZFx1YjI5NCBcdWFjYmRcdWFlMzBcdWM3NTggXHViMGEwXHVjOWRjLCBzXHViMjk0IFx1YzJkY1x1Yzc5MSBcdWMyZGNcdWFjMDQsIGVcdWIyOTQgXHVjODg1XHViOGNjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YzJkY1x1YWMwNFx1Yzc0MCBoaG1tXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViYWE4XHViNGUwIFx1YWNiZFx1YWUzMFx1YjI5NCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHViMGEwXHVjNWQwIFx1YjA1ZFx1YjA5Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCAmcXVvdDtTY2VuYXJpbyAjaTomcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgaVx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YmE3MCAxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Y2MzOFx1YzExZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHViM2M0IFx1YzEyNFx1YmE4NVx1ZDU4OFx1YzljMFx1YjljYywgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzQ0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzVjNlx1YjJlNC4gXHVjOTg5LCBcdWFjYmRcdWFlMzAgQVx1Yzc1OCBcdWM4ODVcdWI4Y2MgXHVjMmRjXHVhYzA0XHVjNzc0IEJcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzJkY1x1YWMwNFx1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBBIFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWJjMTRcdWI4NWMgQlx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVkNTU4XHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3NTA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiIE9seW1waWMgR2FtZXMiLCJkZXNjcmlwdGlvbiI6IjxwPk1pa2UgbG92ZXMgdGhlIG9seW1waWMgZ2FtZXMuIFdoYXQgaGUgaGF0ZXMgYWJvdXQgb2x5bXBpYyBnYW1lcyAmbmRhc2g7IGJlc2lkZXMgdGhlbSB0YWtpbmcgcGxhY2Ugb25seSBvbmNlIGV2ZXJ5IGZvdXIgeWVhcnMgJm5kYXNoOyBpcyB0aGF0IHRoZSBpbmRpdmlkdWFsIGV2ZW50cyBhcmUgc2NoZWR1bGVkIGNvbmN1cnJlbnRseS4gVGhhdCB3YXkgaXQgaXMgbmV2ZXIgcG9zc2libGUgdG8gd2F0Y2ggYWxsIGNvbXBldGl0aW9ucyBsaXZlLiBNaWtlIGFsd2F5cyB0cmllcyB0byBwbGFuIGhpcyBwZXJzb25hbCBzY2hlZHVsZSBpbiBvcmRlciB0byBtYXhpbWl6ZSB0aGUgbnVtYmVyIG9mIGV2ZW50cyBoZSBjYW4gYXR0ZW5kIHRvLiBIb3dldmVyLCBhdCB0aGUgZW5kIGhlIGlzIG5ldmVyIHN1cmUgd2hldGhlciBvciBub3QgaGlzIHNjaGVkdWxlIGFjdHVhbGx5IGlzIG9wdGltYWwuIEhlbHAgaGltITxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgZGF5cyBhbmQgdGltZXMgb24gd2hpY2ggZXZlbnRzIHRha2UgcGxhY2UsIGRldGVybWluZSB0aGUgbWF4aW11bSBudW1iZXIgb2YgZXZlbnRzIE1pa2UgY2FuIHdhdGNoLiBNaWtlIG5ldmVyIGxlYXZlcyBkdXJpbmcgYW4gZXZlbnQsIHNvIGl0IGlzIG5vdCBwb3NzaWJsZSB0byBwYXJ0aWFsbHkgYXR0ZW5kIHRvIGV2ZW50cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIG4sIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciAxICZsZTsgbSAmbGU7IDUwMDAwIHRoYXQgc3BlY2lmaWVzIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGV2ZW50cy4gVGhlIG5leHQgbSBsaW5lcyBkZXNjcmliZSBvbmUgZXZlbnQgd2l0aCB0aHJlZSBpbnRlZ2VycyBkLCBzLCBlLiBUaGUgZXZlbnQgdGFrZXMgcGxhY2Ugb24gZGF5IGQgb2YgdGhlIG9seW1waWNzLCBpdCBzdGFydHMgYXQgcyBhbmQgaXQgZW5kcyBhdCBlLCB3aGVyZSB0aGUgdGltZXMgYXJlIGdpdmVuIGluIHRoZSBmb3JtIGhobW0uIEFsbCBldmVudHMgYXJlIGFzc3VtZWQgdG8gY29uY2x1ZGUgdGhlIHNhbWUgZGF5IHRoZXkgc3RhcnRlZC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBmb3IgZXZlcnkgdGVzdCBjYXNlIGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nICZsZHF1bztTY2VuYXJpbyAjaTomcmRxdW87LCB3aGVyZSBpIGlzIHRoZSBudW1iZXIgb2YgdGhlIHRlc3QgY2FzZSBjb3VudGluZyBmcm9tIDEuIFRoZW4sIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiBldmVudHMgTWlrZSBjYW4gYXR0ZW5kIHRvIGF0IG1vc3QuIFRoZSB0aW1lIGZvciBnZXR0aW5nIGZyb20gb25lIGV2ZW50IHRvIGFub3RoZXIgY2FuIGJlIG5lZ2xlY3RlZC4gRXZlbnRzIHN0YXJ0aW5nIGF0IHRpbWUgdCBjYW4gYmUgc2NoZWR1bGVkIGFmdGVyIGV2ZW50cyBlbmRpbmcgYXQgdCBhcyBsb25nIGFzIHRoZXJlIGFyZSBubyBvdGhlciBjb25mbGljdHMuIFRlcm1pbmF0ZSBlYWNoIHRlc3QgY2FzZSB3aXRoIGFuIGVtcHR5IGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d