Black & White

Given a partially filled grid with M rows and N columns, you are to calculate how many ways there are to fill the remaining part of the grid under the constraints stated below, and output one of these ways (if any exist). Each cell in the grid should be colored either black or white. All black cells in the grid should be connected with each other, and all white cells should also be connected with each other. The pictures below show two filled grids where this constraint is only fulfilled in the right picture. Furthermore, there must be no 2×2 blocks in the grid which consists of only white cells, or of only black cells. The picture below to the left shows a grid with a black and a white 2×2 block, while the grid below to the right contains no such 2×2 block. You are not allowed to change the color of any of the cells whose color has already been assigned in the input, and all cells must be colored Input The first line in the input contains an integer T (less than 100), the number of cases to follow. Each case starts with two integers, M and N (2 ≤ M, N ≤ 8), the number of rows and columns respectively in the grid. The next M lines contains N characters each and describes the grid using the following characters:

- a cell which is colored black

o - a cell which is colored white . - a cell which color has not yet been assigned Output For each case, first output the number of ways to fill the grid. If there are at least one way, you should also output one of these ways, using the same format for the grid as in the input. Output a blank line after each case.

2/3 Sample Input 4 33 o.. .## ... 55 ..#.. ..... ....o o.... .#... 75 ..... ..o.. #.... ..... ..o.. ...#. o.... 23

oo# 68 ........ ........ ........ ........ .#...... ........ Sample Output 4 oo# o## oo# 0 176

#ooo# ###oo #o##o #oooo ####o ooooo 1

3/3 ### oo# 71582 #ooooooo #o#####o #ooooo#o #o#o#o#o #######o #ooooooo