시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 260 90 72 34.123%

문제

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

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

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

입력

입력의 첫째 줄에는 테스트 케이스의 개수 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+XHViYWE4XHViNGUwIFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1Yzg4NVx1YjhjYyBcdWMyZGNcdWFjMDQsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwYTBcdWM5ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVhZTMwXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM1ZDAgXHVjMmRjXHVjNzkxIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzAsIFx1Yzg4NVx1YjhjYyBcdWMyZGNcdWFjMDRcdWM1ZDAgXHViMDk4XHVjNjI0XHVhYzhjXHViNDFjXHViMmU0LiBcdWQ1NWMgXHVhY2JkXHVhZTMwXHViOTdjIFx1YmNmNFx1YjM1OCBcdWM5MTFcdWM1ZDAgXHViMmU0XHViOTc4IFx1YWNiZFx1YWUzMFx1Yjk3YyBcdWJjZjRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWNiZFx1YWUzMFx1YzdhNVx1Yzc0NCBcdWM2MmVcdWFlMzggXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViNjEwLCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NDQgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgXHVjNWM2XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMsIFx1YWNiZFx1YWUzMFx1YWMwMCBcdWMyZGNcdWM3OTFcdWI0MWMgXHVjNzc0XHVkNmM0XHVjNWQwXHViMjk0IFx1YWNiZFx1YWUzMFx1YzdhNVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWMyMTggJm5ic3A7MSAmbGU7IG0gJmxlOyA1MDAwMCBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggZCwgcywgZVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGRcdWIyOTQgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YjBhMFx1YzlkYywgc1x1YjI5NCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0LCBlXHViMjk0IFx1Yzg4NVx1YjhjYyBcdWMyZGNcdWFjMDRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWMyZGNcdWFjMDRcdWM3NDAgaGhtbVx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWFjYmRcdWFlMzBcdWIyOTQgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YjBhMFx1YzVkMCBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgJnF1b3Q7U2NlbmFyaW8gI2k6JnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIGlcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWM3NzRcdWJhNzAgMVx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWNjMzhcdWMxMWRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWFlMzBcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjNjNCBcdWMxMjRcdWJhODVcdWQ1ODhcdWM5YzBcdWI5Y2MsIFx1YWNiZFx1YWUzMFx1YzdhNVx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHVhY2JkXHVhZTMwIEFcdWM3NTggXHVjODg1XHViOGNjIFx1YzJkY1x1YWMwNFx1Yzc3NCBCXHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWMyZGNcdWFjMDRcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgQSBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHViYzE0XHViODVjIEJcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJlNDggXHVjOTA0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzUwNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IiBPbHltcGljIEdhbWVzIiwiZGVzY3JpcHRpb24iOiI8cD5NaWtlIGxvdmVzIHRoZSBvbHltcGljIGdhbWVzLiBXaGF0IGhlIGhhdGVzIGFib3V0IG9seW1waWMgZ2FtZXMgJm5kYXNoOyBiZXNpZGVzIHRoZW0gdGFraW5nIHBsYWNlIG9ubHkgb25jZSBldmVyeSBmb3VyIHllYXJzICZuZGFzaDsgaXMgdGhhdCB0aGUgaW5kaXZpZHVhbCBldmVudHMgYXJlIHNjaGVkdWxlZCBjb25jdXJyZW50bHkuIFRoYXQgd2F5IGl0IGlzIG5ldmVyIHBvc3NpYmxlIHRvIHdhdGNoIGFsbCBjb21wZXRpdGlvbnMgbGl2ZS4gTWlrZSBhbHdheXMgdHJpZXMgdG8gcGxhbiBoaXMgcGVyc29uYWwgc2NoZWR1bGUgaW4gb3JkZXIgdG8gbWF4aW1pemUgdGhlIG51bWJlciBvZiBldmVudHMgaGUgY2FuIGF0dGVuZCB0by4gSG93ZXZlciwgYXQgdGhlIGVuZCBoZSBpcyBuZXZlciBzdXJlIHdoZXRoZXIgb3Igbm90IGhpcyBzY2hlZHVsZSBhY3R1YWxseSBpcyBvcHRpbWFsLiBIZWxwIGhpbSE8XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGRheXMgYW5kIHRpbWVzIG9uIHdoaWNoIGV2ZW50cyB0YWtlIHBsYWNlLCBkZXRlcm1pbmUgdGhlIG1heGltdW0gbnVtYmVyIG9mIGV2ZW50cyBNaWtlIGNhbiB3YXRjaC4gTWlrZSBuZXZlciBsZWF2ZXMgZHVyaW5nIGFuIGV2ZW50LCBzbyBpdCBpcyBub3QgcG9zc2libGUgdG8gcGFydGlhbGx5IGF0dGVuZCB0byBldmVudHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciBuLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgMSAmbGU7IG0gJmxlOyA1MDAwMCB0aGF0IHNwZWNpZmllcyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBldmVudHMuIFRoZSBuZXh0IG0gbGluZXMgZGVzY3JpYmUgb25lIGV2ZW50IHdpdGggdGhyZWUgaW50ZWdlcnMgZCwgcywgZS4gVGhlIGV2ZW50IHRha2VzIHBsYWNlIG9uIGRheSBkIG9mIHRoZSBvbHltcGljcywgaXQgc3RhcnRzIGF0IHMgYW5kIGl0IGVuZHMgYXQgZSwgd2hlcmUgdGhlIHRpbWVzIGFyZSBnaXZlbiBpbiB0aGUgZm9ybSBoaG1tLiBBbGwgZXZlbnRzIGFyZSBhc3N1bWVkIHRvIGNvbmNsdWRlIHRoZSBzYW1lIGRheSB0aGV5IHN0YXJ0ZWQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZm9yIGV2ZXJ5IHRlc3QgY2FzZSBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyAmbGRxdW87U2NlbmFyaW8gI2k6JnJkcXVvOywgd2hlcmUgaSBpcyB0aGUgbnVtYmVyIG9mIHRoZSB0ZXN0IGNhc2UgY291bnRpbmcgZnJvbSAxLiBUaGVuLCBvdXRwdXQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2YgZXZlbnRzIE1pa2UgY2FuIGF0dGVuZCB0byBhdCBtb3N0LiBUaGUgdGltZSBmb3IgZ2V0dGluZyBmcm9tIG9uZSBldmVudCB0byBhbm90aGVyIGNhbiBiZSBuZWdsZWN0ZWQuIEV2ZW50cyBzdGFydGluZyBhdCB0aW1lIHQgY2FuIGJlIHNjaGVkdWxlZCBhZnRlciBldmVudHMgZW5kaW5nIGF0IHQgYXMgbG9uZyBhcyB0aGVyZSBhcmUgbm8gb3RoZXIgY29uZmxpY3RzLiBUZXJtaW5hdGUgZWFjaCB0ZXN0IGNhc2Ugd2l0aCBhbiBlbXB0eSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==