测试数据来自 system/1994

描述

　　考古学家发现了一堵写有未知语言的白色的墙壁。上面有一个N行M列的格子，其中有些格子内被填入了某个A至Z的大写字母，还有一些格子留作空白什么也没有填入。已知横着或竖着的连续若干个字母会形成一个单词，且每一行的阅读顺序有可能是从左往右或从右往左，每一列的阅读顺序也有可能是从上往下或从下往上。也就是说对于一行来说，从左往右可以被看作是若干个单词形成的句子，相邻两个单词被一个或多个空白格子分割开来；也有可能是从右往左被看作是一个句子。竖直方向也有相似的情形。
　　遗憾的是，我们并不完全知道每一行每一列应该有的阅读顺序（从左向右还是从右向左，从上向下还是从下向上）。但是可以猜测，有些单词S会满足翻转过来亦然是一个单词。例如对于英文单词BOY来说，翻转过来YOB也是一个英文单词。
　　此外观察者发现，对于每一行（或列）来说，按照确定后的阅读顺序读出的所有单词同时满足“自己的字典序不小于翻转后的字典序”，或同时满足“自己的字典序不大于翻转后的字典序”。
　　在确定了所有行列的阅读顺序之后，我们可以构造出关于这种未知语言的字典。请问字典中出现的“翻转过来也是一个单词”的单词最少有多少个。请注意，如果一个单词翻转后是不同的另外一个单词，他们需要被分别计入；而对于本身是回文的单词则不需要重复计入。

格式

输入格式

　　第一行一个正整数T，表示有T组测试数据。
　　对于每一组数据来说：第一行输入两个整数N和M。
　　第二行给出了N个数字，对应了N行，其中第i个数字若为1，则表示第i行的阅读顺序从左往右，若为-1，则表示阅读顺序从右往左，若为0，表示无法确定。第三行给出了M个数字，对应了M列，其中第i个数字若为1，则表示第i列的阅读顺序从上往下，若为-1，则阅读顺序从下往上，若为0，表示无法确定。
之后N行，每行给出了长度为M的字符串，由大写字母A到Z和下划线组成，对应了每一个格子内的符号，其中下划线表示这一个格子被留白。

输出格式

输出T行对应T组数据。每一组数据输出一行一个整数，表示最少有多少单词，满足翻转后依然是单词。请注意，一个单词如果是回文的，那么它一定满足“翻转后依然是单词”。

样例1

样例输入1

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

样例输出1

3

限制

对于20%的数据，1<=N，M<=10。
对于60%的数据，每行每列出现的单词不超过6个。
对于100%的数据，1<=N，M<=72，T<=64。

来源

SDOI 2016 round2 day1