Dates

Time limit2sMemory limit1024 MB

Summary

Given the set of digits the calendar can show and a date range, count the days in the range (both ends included) whose DD.MM.YYYY form uses only those digits.

Level: Easy3 of 10
Topics: Implementation, Simulation
Solved: No attempts yet

Statement

Vasya is building his own automatic electronic calendar that shows the current date in the format "DD.MM.YYYY". To do this he needs to display various digits. Right now his calendar can display $k$ different digits. Adding support for each new digit is very laborious, so Vasya will be satisfied if his calendar can show a fairly large number of dates. He therefore wants to know how many days in a given range the calendar can display.

For example, if his calendar can only show the digits 0, 2, and 9, it can show the date "02.02.2009" (the second of February 2009) but cannot show "03.02.2009" (the third of February 2009).

Vasya programs well and knows about leap years, in which February has 29 days. A year is a leap year if its number is divisible by 4 and not divisible by 100, or divisible by 400.

Input

The first line contains an integer $k$ ( $0 \le k \le 10$ ). The second line contains $k$ distinct digits separated by spaces, which the calendar can display. The next two lines contain the first and the last date of the range in the format "DD.MM.YYYY".

Output

Print one integer: the number of days in the range, including both endpoints, on which the calendar can display the date.

Examples2

Example 1
Input
```
3
0 2 9
02.02.2009 
03.02.2009
```
Expected output
```
1
```
Example 2
Input
```
3
0 2 9
01.02.2009
28.02.2009
```
Expected output
```
4
```