Faulty Odometer

Interview

Time limit1sMemory limit128 MB

Summary

Read odometer values that skip the digit 4 and print the true mileage by treating each reading as a base-9 number.

Level: Easy3 of 10
Topics: Math, Implementation, Number theory, Brute force
Solved: No attempts yet

Problem

A car's odometer displays the number of miles traveled as an integer. This odometer has a defect: when counting, it always skips the digit 4, jumping straight from 3 to 5. The defect appears in every position (the ones, the tens, the hundreds, and so on). For example, if the odometer shows 15339 and the car travels one more mile, the reading changes to 15350 instead of 15340.

Input

Each line of input contains a single positive integer between 1 and 999999999 that represents an odometer reading. (Readings never have leading zeros.) The end of input is marked by a line containing a single 0. You may assume that no odometer reading contains the digit 4.

Output

For each line of input, print exactly one line containing, in order: the odometer reading from the input, a colon, a single space, and the actual number of miles the car has traveled.

Examples3

Example 1

Input

Expected output

13: 12
15: 13
2003: 1461
2005: 1462
239: 197
250: 198
1399: 1052
1500: 1053
999999: 531440

Example 2
Input
```
1
0
```
Expected output
```
1: 1
```
Example 3
Input
```
5
0
```
Expected output
```
5: 4
```