Guards at the Museum

Time Limit: 10 Seconds    Memory Limit: 65536 KB

There is a museum in town an there are very valuable items in it.

This museum needs to be guarded. The security department wants you to find a placement for the guards which meet all of their conditions. You are given floor plan of museum, which is a square grid with positioning of walls and items. The criteria are: 

• A guard stands in a cell and doesn't move. A guard can watch over

• Cells in his row or column (up to a wall or item).

• No two guards should see each other.

• All cells in the museum must be watched by some guards.

• Items need to be closely guarded. Each item has a value between 0 and 4 (inclusive), which shows how many guards, should stand next to   that item (“next to here” refer to adjacent horizontally or vertically).   An item with 0 value does not need to be guarded and you should avoid   putting a guard next to it (we need to keep the number of guards low).

Input

The input starts with an integer T, denoting the number of test cases.

Each test case starts with an integer n (5 <= n <= 25), which denotes the size of museum. Then comes n lines, each having n character, representing the layout of museum.

'.' : Empty space

'#' : Wall

'0-4' : An item (number of guards needed around this cell)

Output

For each test case, output the layout of museum with guards in them,

put an 'x' for a guard (without quotes of course). See the sample output for how the layout should look like.

It's guaranteed that answers are unique for input layouts.

Sample Input

1
7
...1.0.
#......
..#.#..
#.....#
..#.3..
......#
.3.2...

Sample Output

..x1.0.
#...x..
x.#.#.x
#...x.#
..#x3x.
.x....#
x3x2x..

Submit

Source: 13th Iran Nationwide Internet Contest - SBU