Problem Statement

Python3 and PyPy3 have a function called eval in their standard library. (Official reference)

This function interprets its argument string as code and returns the result. For example, executing eval("1+1") returns $2$.

A string $X$ satisfying the following conditions is defined as a computable string.

• Each character of $X$ is a digit other than $0$ or an operator (one of 123456789+-).
• The last character of $X$ is a digit other than $0$ (one of 123456789).
• No two operators (each one of +-) are adjacent in $X$.

You are given a string $S$ consisting of digits other than $0$, operators, and ? (each character is one of 123456789+-?).
Consider creating a computable string $S'$ by replacing every ? in $S$ with a digit other than $0$ or an operator (one of 123456789+-), each independently.

Among the computable strings $S'$ that can be generated in this way, find one whose calculation result, when interpreted as a mathematical expression, is the maximum. It is guaranteed that $S'$ can always be generated under the constraints of this problem.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \leq T \leq 10^4$ ($T$ is an integer)
• $1 \leq |S| \leq 5 \times 10^5$ ($|S|$ is the length of $S$)
• For each input, the sum of $|S|$ over all test cases is at most $5 \times 10^5$.
• Each character of $S$ is one of 123456789+-?.
• The last character of $S$ is a digit other than $0$ (one of 123456789) or ?.
• No two operators (each one of +-) are adjacent in $S$.

Input

The input is given from standard input in the following format. Here, $\mathrm{case}_i ~ (i = 1, 2, \cdots, T)$ is the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

$S$

Output

Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

For each test case, print the $S'$, among those that can be generated, whose calculation result, when interpreted as a mathematical expression, is the maximum.

Sample

5
2?-??
-???
?-???-?
3-141+592-653-589+793
????????????????????????????????????????????????????????????????????????????????

29-11
-1+9
9-1+9-1
3-141+592-653-589+793
99999999999999999999999999999999999999999999999999999999999999999999999999999999