Statement

In a grid of square cells, we call the neighbors of a cell the cells directly above, below, to the left, and to the right of this cell. (As the grid is finite, cells on the border have fewer than four neighbors.)

I have a grid of square cells. I will reveal a few facts about it:

  1. It has \(c\) columns and \(r\) rows

  2. Each cell contains either a \(0\) or a \(1\)

  3. Each \(0\) has both a \(0\) and a \(1\) as its neighbor

  4. Each \(1\) does not have both a \(0\) and a \(1\) as its neighbor

  5. The first row matches a pattern \(p\) and the last row matches a pattern \(q\). Note that this can be the same row, i.e. when \(r = 1\). The patterns are strings of exactly \(c\) characters, with the following meaning: if the \(i-th\) character is 0 or 1, then the \(i\)-th cell of the row is a 0 or 1, respectively. Otherwise, the \(i\)-th character is * and the corresponding cell can contain anything.

  6. My grid contains the fewest number of \(1\)s possible given that the previous facts are true.

How many \(1\)s do I have in my grid?

Input format

The first line of each input file contains the number \(t\) of test cases. The descriptions of the individual test cases follow.

Each test case starts with an empty line. The second line contains two positive integers \(c\) and \(r\) (in this order). The third line contains the pattern \(p\) and the fourth line contains the pattern \(q\) (each of length \(c\)).

Output format

For each test case output a single line with a single number: the smallest number of \(1\)s in a grid that matches all the constraints specified above. If there is no grid satisfying these constraints, output \(-1\) instead.

Subproblem F1 (14 points, public)

Input file: F1.in

\(t \leq 10^4\), \(c \leq 7\) and the area of the whole grid is small: \(r \cdot c \leq 21\).

Subproblem F2 (20 points, public)

Input file: F2.in

\(t \leq 500\), \(c \leq 7\) and \(r \leq 50\)

Subproblem F3 (20 points, public)

Input file: F3.in

\(t \leq 10^4\), \(c \leq 7\) and \(r \leq 10^3\)

Subproblem F4 (20 points, secret)

Input file: F4.in

\(t \leq 100\), \(c \leq 7\) and \(r \leq 10^9\)

Subproblem F5 (26 points, secret)

Input file: F5.in

\(t \leq 10^4\), \(c \leq 7\) and \(r \leq 10^{17}\)

Example

input
3

3 3
*10
1*1

7 5
0**0*01
10*01*1

6 47
*0****
0***00
output
3
10
69

One possible arrangement for \(r,c = 3\) is

010
000
101