Go is an adversarial game with the objective of surrounding a larger total area of the board with one's stones than the opponent's. The core idea of the game is the concept of liberty, which is an open point, or rather, an intersection of vertical and horizontal lines on the chessboard with no stones on it, bordering the group.

A stone, white or black, is called alive if it has at least one liberty directly orthogonally adjacent (up, down, left, or right), or must be in the same connected group with a stone of the same color which is alive. We say two stones of the same color are directly connected if they're orthogonally adjacent. We say two stones and of the same color are in the same connected group if there exists a sequence of stones such that for all , and are of the same color and are directly connected.

For example, in the left part of the below figure, neither of the two white stones is alive, as they're captured by the surrounding black stones; While in the right part, the rightmost white stone is also not alive, even if the leftmost black stone is also not alive.
Given a chessboard with vertical and horizontal lines where some stones might be lying on, please calculate the number of white stones captured by the black ones (that is to say, calcaulate the number of white stones not alive). The results for the above examples are and , respectively.

However, our dear friend Kotori thinks that this problem is too simple for our clever contestants to solve, so she would like to heat things up by instead asking you to flip the color of each stone (that is to say, change a black stone to a white one, or vice versa²) independently and find out the corresponding answer after each flip.

There are multiple test cases. The first line of the input contains an integer  indicating the number of test cases. For each test case:

The first line contains one integer  () indicating the length of the board side.

For the next  lines, the -th line contains a string  (  , , ), where  indicates that the intersection on the -th row and the -th column contains a black stone. Similarly  for a white stone and  for an empty intersection.

It's guaranteed that the sum of  over all test cases does not exceed .

For each test case output an integer  modulo  which is the answer encoded as follows:

1. Sort all the stones with their row number (from top to bottom) as the primary sort key and their column number (from left to right) as the secondary sort key;

2. , where  is the number of stones and  is the number of white stones not alive after flipping the color of the -th stone.

NOTE that the MODULUS and the BASE are DIFFERENT.

3
2
.o
..
3
.x.
xoo
ox.
2
oo
oo

0
870527216
485539347

For the second sample test case, after flipping the stones in the order of , , , , , , the number of dead white stones are , , , , , , repectively.

For the third sample test case all stones on the chessboard, black or white, are not alive.