Problem Description

Xiao I and Xiao J are playing a game again.

The game is played on an $n \times m$ grid. We use an ordered pair $(x,y)$ to describe the cell in row $x$ and column $y$, where $1 \le x \le n, 1 \le y \le m$. Initially, at least one cell on the grid is white, and all other cells are black.

Xiao I and Xiao J take turns to make moves, with Xiao I moving first. In each move, the player must choose exactly one white cell and paint it black.

Two cells are considered adjacent if and only if they share an edge. If after some move, cell $(1,1)$ is not white, or cell $(n,m)$ is not white, or it is impossible to start from $(1,1)$ and reach $(n,m)$ by moving each time to an adjacent white cell (that is, $(1,1)$ and $(n,m)$ are not in the same 4-connected component formed by white cells), then the current player loses and the other player wins.

As a spectator, you want to know who will win if both Xiao I and Xiao J play perfectly.

Input Format

This problem contains multiple test cases. The first line contains an integer $T (1 \le T \le 100)$, denoting the number of test cases. Then the test cases follow. For each test case:

• The first line contains two integers $n, m (2 \le n, m \le 1000)$, denoting the size of the grid.
• The next $n$ lines each contain a string of length $m$ over the character set BW, describing the initial coloring of the grid. The $j$-th character in the $i$-th line is B if $(i,j)$ is initially black, otherwise it is W meaning $(i,j)$ is initially white. It is guaranteed that there is at least one white cell on the initial board.

It is guaranteed that, within a single test point, the sum of $n \times m$ over all test cases does not exceed $5 \times 10^6$.

Output Format

For each test case, output one character in one line. If Xiao I has a winning strategy, output I; otherwise, if Xiao J has a winning strategy, output J.

2
2 2
WB
WW
2 2
WW
WW

J
I

Hint

For the first test case, Xiao I can only paint $(2,1)$ black, but painting $(2,1)$ black will make it impossible to move from $(1,1)$ to $(2,2)$ by moving only to adjacent white cells each time. Therefore, no matter how Xiao I plays, Xiao I will lose, so output J.

For the second test case, Xiao I can paint $(1,2)$ black, and then no matter how Xiao J plays, Xiao J will lose, so output I.

Source and Acknowledgements

From the finals of THUPC2024 (the 2024 Tsinghua University Student Programming Contest and Intercollegiate Invitational Contest). Thanks to THUSAA for providing the problem.

For the testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository at https://thusaac.com/public.

Translated by ChatGPT 5