Description

Archaeologists found a white wall written in an unknown language. On it there is an $n$-by-$m$ grid. Some cells contain an uppercase letter from A to Z, and some cells are blank.

A contiguous run of letters strictly horizontally or vertically forms a word. Each row may be read either left to right or right to left, and each column may be read either bottom to top or top to bottom. That is, for each row, reading from left to right can be regarded as a sentence formed by several words, where adjacent words are separated by one or more blank cells; or it may be a sentence read from right to left. The vertical direction is analogous.

Unfortunately, we do not completely know the reading order of each row and each column. However, it is plausible that some words satisfy that their reversed form is also a word. For example, the word BOY and its reversal YOB are both English words.

Furthermore, observers found that for each row (column), under its finalized reading order, all words read in that row (column) simultaneously satisfy either “their own lexicographic order is not less than that of their reversed form,” or simultaneously satisfy “their own lexicographic order is not greater than that of their reversed form.”

After determining the reading order of all rows and columns, we can construct a dictionary for this unknown language.

What is the minimum possible number of distinct words in the dictionary whose reversed form is also a word? Please note that if a word and its reversed form are two different words, they must be counted separately; a word that is itself a palindrome should not be counted twice.

Input Format

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

For each test case:

• The first line contains two integers $n, m$.
• The second line contains $n$ numbers, corresponding to the $n$ rows. If the $i$-th number is 1, the $i$-th row is read left to right; if it is -1, it is read right to left; if it is 0, the direction is undetermined.
• The third line contains $m$ numbers, corresponding to the $m$ columns. If the $i$-th number is 1, the $i$-th column is read top to bottom; if it is -1, it is read bottom to top; if it is 0, the direction is undetermined.
• Then follow $n$ lines. Each line is a string of length $m$, consisting of uppercase letters A to Z and underscores. An underscore denotes an empty cell.

Output Format

Output $T$ lines. For each test case, output a single integer: the minimum number of words such that their reversed form is also a word.

Note that if a word is a palindrome, it certainly satisfies “its reversal is also a word.”

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

3

Hint

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

Translated by ChatGPT 5