Write a program that, given a quantity of money expressed in euro cents, prints the minimal number of coins that you need to reach that quantity. You have an unlimited number of coins of each kind: 1 cents, 2 cents, 5 cents, 10 cents, 20 cents, 50 cents, 100 cents and 200 cents.

Input

The input is a sequence of naturals between 0 and 10^{9}, ended in -1. The
sequence will not contain more than 10000 numbers.

Output

For each quantity of the input, that quantity has to be printed, followed by a colon, a space, and the minimal number of coins that you need to reach that quantity.

Public test cases

**Input**

0 1 4 6 8 89 140 666 1000 999 -1

**Output**

0: 0 1: 1 4: 2 6: 2 8: 3 89: 6 140: 3 666: 7 1000: 5 999: 11

Information

- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++ Java Python