Prefix to Infix Expression Conversion

You are given one or more test cases. Each test case contains several expressions written in prefix notation. Your task is to convert each prefix expression into its corresponding infix expression with proper parenthesization.

The prefix expression consists of an operator (+, -, *, /) and operands represented by single letters. When converting to infix, ensure that each binary operation is enclosed in parentheses. For example, converting the prefix expression + A B should result in (A + B). More complex expressions should also maintain correct ordering and grouping. You may refer to the formula:

\( \text{infix} = (\text{operand}_1 \ operator \ \text{operand}_2) \)

Please note that the input is provided via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The first line contains an integer T (1 ≤ T ≤ 100), the number of test cases. For each test case:

• The first line contains an integer N (1 ≤ N ≤ 100) denoting the number of prefix expressions.
• Then follow N lines, each containing a valid prefix expression consisting of operators (+, -, *, /) and single-letter operands separated by spaces.

All input is read from standard input (stdin).

outputFormat

For each test case, output the corresponding infix expressions, each on a new line in the order they appear in the input. Print all output to standard output (stdout).

## sample

2
3
+ A B
* + A B - C D
+ * A B C
2
- A B
+ + A B C

(A + B)
((A + B) * (C - D))
((A * B) + C)
(A - B)
((A + B) + C)

</p>