Generate Possible Words from T9 Keypad

Given a string S consisting of digits from 2 to 9, the task is to generate all possible strings that can be formed by mapping these digits to letters on a T9 keypad. The resulting strings should be printed in lexicographical order for each test case.

Example:

Input:

S = "34"

Output:

"dg dh di eg eh ei fg fh fi"

Explanation:

Each digit on the T9 keypad can map to multiple letters. For example, 3 maps to 'd', 'e', 'f', and 4 maps to 'g', 'h', 'i'. All combinations are generated and sorted.

Constraints:

• 1 <= T <= 10
• 1 <= |S| <= 7 where |S| is the length of string S
• Each string S contains only digits from 2 to 9

Input:

The first line contains an integer 'T', representing the number of test cases. The following lines contain the string S for each test case.

Output:

For each test case, print all lexicographically sorted possible strings that can be formed. Each result is on a new line.

Note:

You do not need to do any output; just implement the function to return the results.