B. Emily's Agenda
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Emily is very excited to lead a project for the first time, especially one as inspiring as CODEFEM! However, as she quickly learned: "With great power comes great responsibility... and tons of meetings!".

There are meetings scheduled with the marketing team, design team, problem setters, finance, and logistics. As a dedicated leader, Emily wants to attend as many meetings as possible. She has a list of $$$N$$$ scheduled meetings. Each meeting $$$i$$$ has a start time and an end time specified in 24-hour format (HH:MM).

The scheduling rules are as follows:

  • All meetings start during the current day (between 00:00 and 23:59).
  • Emily must attend each chosen meeting from start to finish.
  • She cannot be in two meetings at the same time.
  • A meeting may cross midnight: if its end time is less than or equal to its start time, the meeting ends on the following day.
  • If one meeting ends exactly when another starts, Emily may attend both.

Help Emily organize her agenda and find the maximum number of meetings she can attend.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 100000$$$), the number of scheduled meetings.

Each of the next $$$N$$$ lines contains two space-separated strings, $$$s_i$$$ and $$$e_i$$$, representing the start and end times of the $$$i$$$-th meeting in 24-hour format HH:MM ($$$00 \le HH \le 23$$$, $$$00 \le MM \le 59$$$).

If $$$e_i \le s_i$$$, the meeting crosses midnight: it starts on the current day at $$$s_i$$$ and ends on the following day at $$$e_i$$$. A meeting with $$$s_i = e_i$$$ lasts exactly $$$24$$$ hours.

It is guaranteed that no meeting lasts more than $$$24$$$ hours.

Output

Print a single integer: the maximum number of meetings Emily can attend.

Examples
Input
4
09:00 11:00
10:30 12:30
11:00 13:00
23:00 01:00
Output
3
Input
3
10:00 18:00
11:00 14:00
12:00 13:00
Output
1
Note

In the first example, the meeting 23:00–01:00 crosses midnight: it starts at 23:00 of the current day and ends at 01:00 of the following day. Emily can attend 09:00–11:00 and 11:00–13:00 back to back (the second starts exactly when the first ends), and then 23:00–01:00, for a total of $$$3$$$ meetings.

In the second example, the three meetings all overlap with each other (in particular, 11:00–14:00 and 12:00–13:00 are contained in 10:00–18:00), so Emily can attend at most one of them. The answer is $$$1$$$.