#P1434. [ZJOI2009]染色游戏

[ZJOI2009]染色游戏

Description

一共n×m个硬币,摆成n×m的长方形。dongdong和xixi玩一个游戏,每次可以选择一个连通块,并把其中的硬币全

部翻转,但是需要满足存在一个硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正上方)

,并且这个硬币是从反面向上翻成正面向上。dongdong和xixi轮流操作。如果某一方无法操作,那么他(她)就输了

。dongdong先进行第一步操作,假设双方都采用最优策略。问dongdong是否有必胜策略。

Input

第一行一个数T,表示他们一共玩T局游戏。

接下来是T组游戏描述。每组游戏第一行两个数n;m,

接下来n行每行m个字符,第i行第j个字符如果是“H”表示第i行第j列的硬币是正面向上,

否则是反面向上。第i行j列的左上方是指行不超过i并且列不超过j的区域。

1≤n;m≤100,1≤T≤50。

Output

对于每局游戏,输出一行。

如果dongdong 存在必胜策略则输出“- -”(不含 引号) 否则输出“= =”(不含引号)。

(注意输出的都是半角符号,即三个符号 ASCII 码分别为45,61,95)

Samples

32
3
HHH
HHH
2 3
HHH
TTH
2 1
T
H
= =
- -
- -