Color the chessboard

Problem Description

There is a chessboard with $n$ rows and $m$ columns, at first every position is colored red or blue or white. HazelFan want to change the color of every white position into red one or blue one, so that every rectangle in the chessboard with even rows and even colums, contains same number of red positions and blue positions. HazelFan wants to know how many ways are there to color the chessboard, module $998244353$.

Input

The first line contains a positive integer $T(1\leq T\leq5)$, denoting the number of test cases. For each test case: The first line contains two positive integers $n,m(1\leq n,m\leq10^3)$. The next $n$ lines, the $i$th line contains a string of length $m$, the $j$th character describes the position in the $i$th row and the $j$th column as below: 'R': the position is colored red. 'B': the position is colored blue. '?': the position is colored white.

Output

For each test case: A single line contains a nonnegative integer, denoting the answer.

Sample Input

2

2 2

RB

??

3 3

???

?R?

???

Sample Output

2

7

Source

2017 Multi-University Training Contest - Team 7

https://acm.hdu.edu.cn/showproblem.php?pid=6122