[ZJOI2009]染色游戏
题号：NC20487
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一共n × m 个硬币，摆成n × m 的长方形。dongdong 和xixi 玩一个游戏， 每次可以选择一个连通块，并把其中的硬币全部翻转，但是需要满足存在一个 硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正上方)，并且这个硬币是从反面向上翻成正面向上。
dongdong和xixi轮流操作。 如果某一方无法操作，那么他(她) 就输了。dongdong 先进行第一步操作，假 设双方都采用最优策略。问dongdong 是否有必胜策略。

输入描述:

第一行一个数T，表示他们一共玩T局游戏。
接下来是T组游戏描述。每组游戏第一行两个数n,m，
接下来n 行每行m 个字符，第i行第j个字符如果是“H” 表示第i行第j列的硬币是正面向上，否则是反面向上。第i行j列的左上方是指行不超过i 并且列不超过j的区域。

输出描述:

对于每局游戏，输出一行。如果dongdong 存在必胜策略则输出“-_-”(不含 引号) 否则输出“=_=”(不含引号)。(注意输出的都是半角符号，即三个符号 ASCII 码分别为45,61,95)
示例1

输入

复制 
3
2 3
HHH
HHH
2 3
HHH
TTH
2 1
T
H

输出

复制 
=_=
-_-
-_-

备注:

对于40% 的数据，满足。
对于100% 的数据，满足。