Archaeologists have discovered a white wall inscribed with an unknown language, featuring a grid of $n$ rows and $m$ columns. Some cells contain uppercase letters from A to Z, while others are blank. A sequence of consecutive letters in a row or column forms a word. The reading direction for each row can be either left-to-right or right-to-left, and for each column, it can be either top-to-bottom or bottom-to-top. Specifically, for any given row, the sequence of characters read in the chosen direction can be viewed as a sentence consisting of several words separated by one or more blank cells; the same applies to columns.

Unfortunately, the reading direction for each row and column is not fully known. However, it is hypothesized that some words satisfy the property that their reverse is also a word. For example, the word BOY, when reversed, becomes YOB, which is also an English word. Furthermore, observers have noted that for each row (or column), all words read according to the determined direction must either all satisfy the condition that "the word's lexicographical order is no less than its reverse's lexicographical order," or all satisfy the condition that "the word's lexicographical order is no greater than its reverse's lexicographical order."

Once the reading directions for all rows and columns are determined, we can construct a dictionary for this unknown language. What is the minimum number of words in the dictionary that "remain a word when reversed"? Note that if a word is different from its reverse, both must be counted; if a word is a palindrome, it is counted only once.

Input

The first line contains an integer $T$, representing the number of test cases.

For each test case:

• The first line contains two integers $n$ and $m$.
• The second line contains $n$ integers corresponding to the $n$ rows. If the $i$-th integer is 1, the reading direction for the $i$-th row is left-to-right; if -1, it is right-to-left; if 0, the direction is undetermined.
• The third line contains $m$ integers corresponding to the $m$ columns. If the $i$-th integer is 1, the reading direction for the $i$-th column is top-to-bottom; if -1, it is bottom-to-top; if 0, the direction is undetermined.
• The following $n$ lines each contain a string of length $m$ consisting of A~Z and underscores (_), representing the symbols in each cell, where an underscore represents an empty cell.

Output

Output $T$ lines. Each line should contain a single integer representing the minimum number of words that remain a word when reversed.

Note: If a word is a palindrome, it automatically satisfies the condition of "remaining a word when reversed."

Examples

Input 1

1
2 10
0 0
0 0 0 0 0 0 0 0 0 0
ADA_JARVIS
ADA_SIVRAJ

Output 1

3

Subtasks

For $100\%$ of the data, $1 \leq n,m \leq 72, \ T \leq 64$.