Big Brick

During that quarantine Amelia was remembering what she liked to do as a child. Nostalgically, she remembered how much she enjoyed playing Snake on her mother's cell phone. It was the famous 'brick' of the Aikon brand. She even managed to find an Android application that simulated the game, but she started to ask herself: "How could I write messages with that keyboard?". In the image below there is a picture of the cell phone on the left and the detail of its keyboard on the right.

She remembered how the keyboard was used to write messages. In this problem, for the sake of simplicity, we will consider a mobile phone in English (there are no accents).

The keys 2 to 9 are used to type the letters 'a' to 'z', and they work like this: if we want to get one of the letters associated with one of the keys, we need to press it a number of times equal to the position of the letter desired. For example, pressing the 6 key once we get ‘m’. If we press again, we’ll get ‘n’ and then ‘o’. If we keep pressing it we will get the number ‘6’ and then start over at ‘m’, so on. The 0 key is used to insert spaces in the message; the key 1 was just the digit '1' and some punctuation (which will not be used in this problem) and the key # is used to capitalize the next letter, for example, if you press # 2 we will get 'A', if you press # 27 we will get 'Ap'.

In the case that we have two consecutive letters in the message that are formed by the same key, it was necessary to wait a while to continue typing, in this problem we will consider which key * represents this time interval, that is, the function of the key * in our case is to separate the sequences of two letter presses on the same key. For example, to type the word 'cafe', the keystroke sequence would be as follows: 222 * 2333 * 33. But if the second letter on the same key is capitalized, there is no need to press ‘*’ because you’ll have to press ‘#’ between them. For example, the word 'cAfe' corresponds to the sequence 222 # 2333 * 33.

As the keyboard was so hard, Amelia hated making mistakes, so she wants to know the minimum sequence of keys she must press to type each message.