Given a string s containing digits from 2 to 9 inclusive, write a program to return all possible letter combinations that the number could represent according to the mapping of digits to letters on a telephone keypad (image below). The letter combinations should be printed in lexicographical order.
Input
The input consists of a single line containing the string s (1 ≤ |s| ≤ 10), where |s| represents the length of the string. The string s consists of digits from 2 to 9 inclusive.
Output
Output all possible letter combinations that can be formed by the given s, with each combination printed on a separate line. The letter combinations should be printed in lexicographical order.