At the risk of its future, International Cellular Phones Corporation (ICPC) invests its resources in developing new mobile phones, which are planned to be equipped with Web browser, mailer, instant messenger, and many other advanced communication tools. Unless members of ICPC can complete this stiff job, it will eventually lose its market share.
You are now requested to help ICPC to develop intriguing text input software for small mobile terminals. As you may know, most phones today have twelve buttons. namely, ten number buttons from 0 to 9 and two special buttons * and #. Although, the company is very ambitious, it has decided to follow today's standards and conventions. You should not change the standard button layout, and should also pay attention to the following standard button assignment.
BUTTON LETTERS BUTTON LETTERS
2 a,b,c 6 m,n,o
3 d,e,f 7 p,q,r,s
4 g,h,i 8 t,u,v
5 j,k,l 9 w,x,y,z
This means that you can only use eight buttons for text input.
Most users of current ICPC phones are rushed enough to grudge wasting time on even a single button press. Your text input software should be economical of user's time so that a single button press is sufficient for each character input. In consequence, for instance, your program should accept a sequence of button presses "77377" and produce the word "press". Similarly, it should translate "77377843288866" into "press the button".
However, it seems impossible to build such text input software since more than one English letter is represented by a digit! For instance, "77377" may represent not only "press" but also any one of 768 (4*4*3*4*4) character strings. However, we have the good news that the new model of ICPC mobile phones has enough memory to keep a dictionary. You may be able to write a program that filters out false words, i.e. strings not listed in the dictionary.