Kruskal-chan recently came up with a new idea.

"If you can only see half of the information, can you still deduce the other half?" she muttered to herself while drawing small squares on a piece of scratch paper.

A junior in her club leaned over to take a look: "Huh? Isn't this Minesweeper? Why is there only one row on top?"

"This is called 'Semi-Information Minesweeper'!" Kruskal-chan raised her pen triumphantly, "True reasoning isn't about guessing; it's about necessity!"

She pushed the board, which only showed the information for the first row, toward you and tapped the table lightly.

"Give it a try — can you determine which cells in the second row must be mines, which must be empty, and which are impossible to determine?"

You are playing a special game of Minesweeper. The game is played on a $2 \times n$ grid, where each cell is either a mine or an empty space.

You already know whether each cell in the first row is a mine or an empty space; if a cell is empty, you also see a number representing the total number of mines in the eight adjacent cells surrounding it.

Now, you need to infer, based on this information, whether each cell in the second row is definitely a mine, definitely an empty space, or impossible to determine. It is guaranteed that there exists at least one configuration of the second row that satisfies all the conditions of the first row.

Input

The input contains multiple test cases.

The first line contains a single positive integer $T$, representing the number of test cases.

Each of the following lines represents a test case, containing a string of length $n$ ($1 \le n \le 3 \times 10^5$), where the $i$-th character represents the state of the $i$-th cell in the first row:

• If the cell is a mine, it is represented by the character *.
• If the cell is an empty space, it is represented by a digit character from 0 to 8, indicating the total number of mines in the eight adjacent cells surrounding that cell.

It is guaranteed that $\sum n \le 3 \times 10^5$, and for each test case, there exists at least one configuration of the second row that satisfies all the conditions of the first row.

Output

For each test case, output a string of length $n$, where the $i$-th character represents the result of the deduction for the $i$-th cell in the second row:

• If it must be a mine, output *.
• If it must be an empty space, output ..
• If it is impossible to determine, output ?.

Examples

Input 1

6
*
111
12*21
11112221
*2*3*4*5*
*32*3*23*

Output 1

?
.*.
??.??
??.??*??
...???***
*??.*.??*