False Alarm
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Faina is going to sleep, but she needs to wake up early tomorrow for a very important contest. She has already set $$$n$$$ alarms at different times between 7:00 and 9:00 in the morning.

However, Faina is a deep sleeper. She knows that in order to wake up, she will need to hear at least three alarms within a 10-minute timespan. In other words, for some three alarms, the difference between the first and the last alarm must be 10 minutes or less.

Faina is not sure if the current set of alarms she has satisfies this condition, and she is worried she might oversleep the contest (and make her teammates angry!). Thus, she wants to set some additional alarms. All new alarms should also be set between 7:00 and 9:00, and all alarms, including the old ones, must be set at different times.

Find the smallest number of additional alarms Faina has to set to be confident that she will wake up. In particular, if she can already be sure she'll wake up, the number of additional alarms is $$$0$$$.

Input

The first line contains a single integer $$$n$$$, denoting the number of alarms Faina has set ($$$1 \le n \le 20$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains the time of the $$$i$$$-th alarm in the h:mm format ($$$7 \le \mathtt{h} \le 9$$$; $$$00 \le \mathtt{mm} \le 59$$$; if $$$\mathtt{h} = 9$$$, then $$$\mathtt{mm} = 00$$$). The alarms are given in strictly increasing order of time.

Output

Print the smallest number of additional alarms Faina has to set in order to guarantee waking up.

Examples

Input
5
7:47
7:56
7:59
8:05
8:13
Output
0
Input
7
8:00
8:10
8:20
8:30
8:40
8:50
9:00
Output
1
Input
3
7:13
7:41
8:36
Output
2

Note

In the first test, three alarms at 7:56, 7:59, and 8:05 guarantee that Faina will wake up.

In the second test, any time between 8:00 and 9:00 that does not coincide with existing alarms works.

In the third test, one possible solution is to set two more alarms at 7:45 and 7:46.