409950: GYM103861 H Check Pattern is Good

H. Check Pattern is Goodtime limit per test10 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Prof. Shou is given an $$$n\times m$$$ board. Some cells are colored black, some cells are colored white, and others are uncolored.

Prof. Shou likes check patterns, so he wants to color all uncolored cells and maximizes the number of check patterns on the board.

$$$4$$$ cells forming a $$$2\times 2$$$ square are said to have the check pattern if they are colored in one of the following ways:

BW

WB

or

WB

BW

. Here 'W' ("wakuda" in Chewa language) means the cell is colored black and 'B' ("biancu" in Corsican language) means the cell is colored white.

Input

The first line contains a single integer $$$T$$$ $$$(1\leq T \leq 10^4)$$$ denoting the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n, m\le 100$$$) denoting the dimensions of the board.

Each of the next $$$n$$$ lines contains $$$m$$$ characters. The $$$j$$$-th character of the $$$i$$$-th line represents the status of the cell on the $$$i$$$-th row and $$$j$$$-th column of the board. The character is 'W' if the cell is colored black, 'B' if the cell is colored white, and '?' if the cell is uncolored.

It is guaranteed that the sum of $$$nm$$$ over all test cases is no more than $$$10^6$$$.

Output

For each test case, output a line containing the maximum number of check patterns on the board.

In the next $$$n$$$ lines, output the colored board in the same format as the input. The output board should satisfy the following conditions.

• It consists of only 'B' and 'W'.
• If a cell is already colored in the input, its color cannot be changed in the output.
• The number of check patterns equals the answer you print.

If there are multiple solutions, output any of them.

ExampleInput

3
2 2
??
??
3 3
BW?
W?B
?BW
3 3
BW?
W?W
?W?

Output

1
WB
BW
1
BWB
WWB
BBW
4
BWB
WBW
BWB