Olympic Games

Interview

Time limit2sMemory limit256 MB

Summary

Given each event's date and start and end times in hhmm, find the maximum number of events a person can attend without overlap, moving freely between venues.

Level: Medium5 of 10
Topics: Greedy, Sorting, Intervals, Implementation
Solved: No attempts yet

Problem

Sanggeun both loves and hates the Olympics. He loves them because he gets to watch many different sporting events, and he hates them because several events run at the same time, so he cannot watch all of them live.

He has just arrived at the Olympic venues. Given the date, start time, and end time of every event, determine the maximum number of events Sanggeun can watch live.

The rules are as follows.

Sanggeun enters a venue at an event's start time and leaves at its end time.
While watching one event he cannot move to another venue in the middle of it.
Moving between venues takes no time. Therefore, if one event's end time equals another event's start time, he can finish the first event and immediately move on to the next one.
Once an event has already started, he can no longer enter that venue.

Input

The first line contains the number of test cases $n$ .

The first line of each test case contains the number of events $m$ ( $1 \le m \le 50000$ ). Each of the next $m$ lines contains three integers $d$ , $s$ , and $e$ describing one event, where $d$ is the date the event is held, $s$ is its start time, and $e$ is its end time. Times are given in hhmm format, and every event ends on the day it starts.

Output

For each test case, first print Scenario #i:, where $i$ is the test case number starting from 1. On the next line, print the maximum number of events Sanggeun can watch. Print one blank line between the outputs of consecutive test cases.

Examples2

Example 1

Input

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

Expected output

Scenario #1:
7

Scenario #2:
2

Example 2
Input
```
1
1
1 0900 1000
```
Expected output
```
Scenario #1:
1
```