Camping

Time limit1sMemory limit128 MB

Summary

Given limits L, P, V, find the most days out of V that satisfy using at most L days in any window of P consecutive days.

Level: Medium5 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

Mountaineer Kim Kangsan went camping with his family. However, the campsite had the following warning posted:

This campsite may only be used for 10 days out of any 20 consecutive days.

Kangsan has just started a 28-day vacation. During this vacation, at most how many days can Kangsan use the campsite?

Kangsan wants to solve a more general version of the problem. The campsite may be used for only $L$ days out of every $P$ consecutive days, and Kangsan's vacation lasts $V$ days. Find the maximum number of days Kangsan can use the campsite (where $1 < L < P < V$ ).

Input

The input consists of several test cases. Each test case is given on a single line containing three integers $L$ , $P$ , and $V$ in that order. All integers fit within the int range. The last line of the input contains 0 0 0, which must not be processed.

Output

For each test case, print the maximum number of days Kangsan can use the campsite, one per line, in the format Case x: y, where x is the test case number starting from 1 and y is the answer.

Examples5

Example 1

Input

5 8 20
5 8 17
0 0 0

Expected output

Case 1: 14
Case 2: 11

Example 2
Input
```
10 20 28
0 0 0
```
Expected output
```
Case 1: 18
```
Example 3
Input
```
2 10 13
0 0 0
```
Expected output
```
Case 1: 4
```
Example 4
Input
```
2 3 4
0 0 0
```
Expected output
```
Case 1: 3
```

Example 5

Input

Expected output

Case 1: 14
Case 2: 9
Case 3: 17