Description

There are $n \times m$ coins arranged in an $n \times m$ rectangle. Dongdong and Xixi play a game. In each move, a player may choose a connected component and flip all coins in it, but the move must satisfy: there exists a coin in this component such that all other coins in the component are in its upper-left (including directly to its left or directly above), and this coin is flipped from tails-up to heads-up. Dongdong and Xixi take turns. If a player cannot move, he or she loses. Dongdong moves first. Assuming both play optimally, determine whether Dongdong has a winning strategy.

Input Format

The first line contains a number $T$, the number of games they play.

Then follow $T$ game descriptions. For each game, the first line contains two numbers $n, m$.

Then there are $n$ lines, each with $m$ characters. In the $i$-th line, the $j$-th character is H if the coin at row $i$, column $j$ is heads-up; otherwise it is tails-up. The upper-left of cell $(i, j)$ refers to the region with row index not exceeding $i$ and column index not exceeding $j$.

Output Format

For each game, output one line. If Dongdong has a winning strategy, output -_-; otherwise, output =_=. Note that these are half-width characters, i.e., the three characters have ASCII codes 45, 61, and 95.

3
2 3
HHH
HHH
2 3
HHH
TTH
2 1
T
H

=_=
-_-
-_-

Hint

For $40\%$ of the testdata, $1 \le n,m \le 5$.

For $100\%$ of the testdata, $1 \le n,m \le 100, 1 \le T \le 50$.

Translated by ChatGPT 5