How much can he sleep? P13289

[r]

Richi is a student with notable characteristics, one of which is his habit of sleeping. Now he is planning one of his usual travels, with many activities, to which he will assist even if they overlap. During his spare time he wants to sleep, but he has decided that only if he can do it for exactly 8 hours (sleeping for less time would be silly). If, when he wakes up, he can sleep for exactly 8 more hours, he will keep sleeping, and so on. How many hours can he sleep in total?

Input

Input consists of several cases. Each case begins with the starting time of the trip s and the ending time of the trip e, two natural numbers such that s < e ≤ 10⁸. Then comes the number of activities n, followed by n descriptions of activities in any order: two natural numbers a and b separated by a hyphen, and such that s ≤ a < b ≤ e. Input ends with two zeros. Suppose n ≤ 10⁵.

Output

For every test case, print a line with the case number and how many hours Richi can sleep, following the format of the sample output.