There are $n \times m$ coins arranged in an $n \times m$ rectangle. dongdong and xixi are playing a game. In each turn, a player can choose a connected component of coins and flip all of them. This move must satisfy the condition that there exists a coin in this connected component such that all other coins in the component are located to its top-left (which includes directly above or directly to the left), and this specific coin must be flipped from tails to heads. dongdong and xixi take turns. If a player cannot make a move, they lose. dongdong goes first. Assuming both players play optimally, determine if dongdong has a winning strategy.

Input

The first line contains an integer $T$, representing the total number of games. This is followed by $T$ game descriptions. Each game starts with a line containing two integers $n$ and $m$. The next $n$ lines each contain $m$ characters. The $j$-th character in the $i$-th line is "H" if the coin at row $i$, column $j$ is heads-up, otherwise it is tails-up. The "top-left" of the coin at row $i$, column $j$ refers to the region where the row index is at most $i$ and the column index is at most $j$.

Output

For each game, output a single line. If dongdong has a winning strategy, output "--". Otherwise, output "==". (Note: use half-width characters; the symbols are '-', '=', and '_').

Examples

Input 1

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

Output 1

==
--
--

Constraints

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

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