Description

Given a grid with n*m grid points and (n-1)*(m-1) blocks. There may be a number of 0 or 1 in some block, represents the number of lines surround this block is odd or even.(0 for even and 1 for odd) When there is no number, there is no limit to the number of lines surround this block.

You have to draw lines between the grid points to form several cycles (a cycle in the grid is a non-empty trail in which the only repeated grid points are the first and last grid points). Two cycles can share grid points but can not share lines.

Please find the number of different solution modulo 998244353. When a line exists in one solution and does not exist in the other solution, the two solutions are considered different.

Format

Input

The first line contains a single integer $t$ $(t \leqslant 100)$ representing the number of test cases in the input. Then t test cases follow.

The first line of each test case contains two integers $n$ and $m$ $(2 \leqslant n,m \leqslant 17)$ representing the height and width of the grid.

Then n-1 lines followed. The i-th of these lines contains m-1 integers, representing the number in the grid. If there is no number, use '.' instead.

The number of test witch $n, m \geqslant 10$ does not exceed 5.

Output

For each test case, print one integer in one line, which is the answer modulo 998244353.

Samples

2
3 3
01
1.
3 4
111
1..

4
4