Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Sleeping

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne day Vasya was lying in bed watching his electronic clock to fall asleep quicker.

Vasya lives in a strange country, where days have *h* hours, and every hour has *m* minutes. Clock shows time in decimal number system, in format H:M, where the string H always has a fixed length equal to the number of digits in the decimal representation of number *h* - 1. To achieve this, leading zeros are added if necessary. The string M has a similar format, and its length is always equal to the number of digits in the decimal representation of number *m* - 1. For example, if *h* = 17, *m* = 1000, then time equal to 13 hours and 75 minutes will be displayed as "13:075".

Vasya had been watching the clock from *h*_{1} hours *m*_{1} minutes to *h*_{2} hours *m*_{2} minutes inclusive, and then he fell asleep. Now he asks you to count how many times he saw the moment at which at least *k* digits changed on the clock simultaneously.

For example, when switching 04:19 → 04:20 two digits change. When switching 23:59 → 00:00, four digits change.

Consider that Vasya has been watching the clock for strictly less than one day. Note that the last time Vasya saw on the clock before falling asleep was "h2:m2". That is, Vasya didn't see the moment at which time "h2:m2" switched to the next value.

Input

The first line of the input file contains three space-separated integers *h*, *m* and *k* (2 ≤ *h*, *m* ≤ 10^{9}, 1 ≤ *k* ≤ 20). The second line contains space-separated integers *h*_{1}, *m*_{1} (0 ≤ *h*_{1} < *h*, 0 ≤ *m*_{1} < *m*). The third line contains space-separated integers *h*_{2}, *m*_{2} (0 ≤ *h*_{2} < *h*, 0 ≤ *m*_{2} < *m*).

Output

Print a single number — the number of times Vasya saw the moment of changing at least *k* digits simultaneously.

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin stream (also you may use the %I64d specificator).

Examples

Input

5 5 2

4 4

2 1

Output

3

Input

24 60 1

0 0

23 59

Output

1439

Input

24 60 3

23 59

23 59

Output

0

Note

In the first example Vasya will see the following moments of time: 4:4 0:0 → 0:1 → 0:2 → 0:3 → 0:4 1:0 → 1:1 → 1:2 → 1:3 → 1:4 2:0 → 2:1 → 2:2 → 2:3 → 2:4. Double arrow () marks the sought moments of time (in this example — when Vasya sees two numbers changing simultaneously).

In the second example *k* = 1. Any switching time can be accepted, since during switching of the clock at least one digit is changed. Total switching equals to 24·60 = 1440, but Vasya have not seen one of them — the switching of 23:59 00:00.

In the third example Vasya fell asleep immediately after he began to look at the clock, so he did not see any change.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/12/2021 05:21:06 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|