During this week, the service of Jutge.org may be disrupted by major platform upgrades.

Little James is excitedly playing the Game of the Goose. Assume that there are three kinds of squares:

A ‘.’ corresponds to a regular square: when a player lands there, his turn ends.

Digits ‘1’ to ‘9’ correspond to penalty squares (inn, prison,…): when a player lands there, his turn ends, and he needs to skip as many of the next turns as the number indicates.

Letters ‘A’ to ‘Z’ correspond to bonus squares (goose, bridge,…): when a player lands there, he moves to the next bonus square of the same type and rolls the die again within the same turn. If he lands on the last bonus square of its type, his turn ends directly, i.e., the square behaves as a ‘.’.

Players start at the first square, and win when they go past the last square of the board. Each (non-penalty) turn consists in rolling a die with numbers from 1 to 6 and moving forward as many steps as the die marked. The turn ends when landing on a non-bonus square.

Input

Input consists of several boards,
each one represented by a string with between 1 and 10^{4} characters
chosen among ‘.’, ‘1’ to ‘9’, and ‘A’ to ‘Z’.
The first character is always a period.

Output

For each case, print the average number of turns a player will take to win in the given board, up to three decimal places. The input cases do not have precision issues.

Public test cases

**Input**

. .2 ...... .ZZZZ ....A...1...A.B.2...A..B....

**Output**

1.000 1.500 2.161 1.222 6.663

Information

- Author
- Edgar Gonzalez
- Language
- English
- Official solutions
- C++
- User solutions
- C++