Letter Combinations of a Phone Number

Given a string containing digits from '2' to '9', return all possible letter combinations that the number could represent. The mapping from digits to letters is given by the telephone buttons: \(2:abc, 3:def, 4:ghi, 5:jkl, 6:mno, 7:pqrs, 8:tuv, 9:wxyz\).

For each test case, output all possible combinations in lexicographical order.

inputFormat

The first line contains an integer \(t\) (\(1 \leq t \leq 10\)) denoting the number of test cases. Each of the next \(t\) lines contains a non-empty string of digits (each from '2' to '9') with length at most 4.

outputFormat

Output a JSON array of \(t\) arrays. Each inner array contains all possible letter combinations for the corresponding test case in lexicographical order.

2
23
7

[["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"],
["p", "q", "r", "s"]]