시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 180 73 61 39.869%

문제

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

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

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

입력

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

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

출력

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

예제 입력

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

예제 출력

Scenario #1:
7

Scenario #2:
2

힌트