### Problem Statement

With the advent of text messaging on cell phones, a new method for typing has evolved, called T9. The way T9 works is it has a dictionary of words, where each letter is mapped to a number 2-9. The number-letter mappings are fixed, and are printed on the number keys of the phone. For example, 2 corresponds to 'a', 'b', and 'c'. A word is defined as a sequence of lowercase letters. Since most words use different digits for their characters, it is possible to determine which word a user is typing by matching the digit sequence to the letter sequence. Below are all the mappings for the characters used in the problem:

```2 - abc
3 - def
4 - ghi
5 - jkl
6 - mno
7 - pqrs
8 - tuv
9 - wxyz
# - <space>
0 - <next word>
```

So for example, to type "hello world", you would press "43556#96753". A conflict arises when two words have the same digit sequence. So for example, "the" and "tie" both have the same digit sequence - "843". The way T9 handles these conflicts is to display the word that comes first alphabetically. Then, if the word isn't desired, the user must press 0 to get the next word alphabetically, and repeat until the desired word is shown. If the user wishes to enter another word, he/she presses # to insert a space and starts entering the next word. So to input "the tie", you would type "843#8430". It is illegal to press a non-zero digit immediately after pressing '0', the only legal keys you can press after pressing '0' are '0' and '#'.

You will be given a String[] messages, which consists of messages you are to type into your cell phone. messages will only contain spaces and words made entirely of lowercase letters. Assume that the words contained in all of the messages are exactly the words contained in the T9 dictionary. Return a String[] where each element i contains the numeric keypresses you would have to type for element i of messages. Note that messages do not necessarily have to contain words, and can contain sequences of multiple spaces which must be preserved.

### Definition

 Class: T9Input Method: getKeypresses Parameters: String[] Returns: String[] Method signature: String[] getKeypresses(String[] messages) (be sure your method is public)

### Constraints

-messages will have between 1 and 50 elements, inclusive.
-Each element of messages will have between 0 and 50 characters, inclusive.
-Each element of messages will contain only lowercase letters ('a'-'z') and spaces.
-There will not be more than 7 words which have the same digit sequence.

### Examples

0)

 `{"the tie", "the tie"}`
`Returns: { "843#8430",  "843#8430" }`
 The example from the problem statement.
1)

 `{" hey joe ", " "}`
`Returns: { "#439#563###",  "###" }`
 Don't forget to preserve multiple spaces, and to handle messages where there are no words.
2)

 `{"cba cba cba cba cba cba cba cba", "abc acb bac bca cab cba"}`
```Returns:
{ "22200000#22200000#22200000#22200000#22200000#22200000#22200000#22200000",
"222#2220#22200#222000#2220000#22200000" }```
 Remember that the dictionary contains all words from all the messages, not just the message you are working on.
3)

 ```{ "the longest case for t nine is probably when", "you enter seven two letter sequences from the", "same key and then repeat the alphabetically", "last case over and over again for the entire", "list of messages", "", "these paragraphs demonstrate how efficient t", "nine is since there is only one time where you", "must use the zero key"}```
```Returns:
{ "843#5664378#2273#367#8#6463#47#77622259#9436",
"968#36837#73836#896#538837#737836237#3766#843",
"7263#539#263#8436#737328#843#25742238422559",
"5278#2273#6837#263#6837#24246#367#843#368473",
"5478#63#63772437",
"",
"843730#7272472747#33666787283#469#333424368#8",
"6463#47#74623#84373#47#6659#663#8463#94373#968",
"6878#873#843#9376#539" }```
4)

 `{"cca ccc c cccb ccca cccc"}`
`Returns: { "222#2220#2#22220#2222#222200" }`
 Note that to make "cccc", you cannot use "22202". Pressing '2' after pressing '0' is illegal.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1966

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4706&pm=1966

schveiguy

#### Testers:

lbackstrom , vorthys

#### Problem categories:

Simple Search, Iteration, String Manipulation