Frozen Food

Interview

Time limit1sMemory limit128 MB

Summary

Count the minutes from a start time to an end time, inclusive, whose HH:MM display contains the digit N at least once.

Level: Medium4 of 10
Topics: Implementation, Simulation, Math, Brute force
Solved: No attempts yet

Problem

Jimin, who has been living on his own for a year, loves frozen food.

As usual, Jimin is heating frozen food in the microwave today. Waiting for the food to warm up is so boring that he decides to count how many of the times shown on the microwave display, in the form HH:MM, contain the digit $N$ . Hours and minutes are always shown with two digits, with a leading 0 for single-digit values (for example, 09:05).

Write a program that counts how many times from the start time to the end time, inclusive, contain the digit $N$ at least once.

Input

The first line gives the start time and the second line gives the end time. Each time consists of two integers, the hour $H$ ( $0 \le H \le 23$ ) and the minute $M$ ( $0 \le M \le 59$ ), separated by a space. The third line gives the digit $N$ ( $0 \le N \le 9$ ) to count.

No input crosses midnight, such as 23:50 to 01:30. In other words, the start time is never later than the end time.

Output

Print the number of times from the start time to the end time that contain the digit $N$ .

Examples1

Example 1
Input
```
15 20
16 0
2
```
Expected output
```
13
```