During the day, your friends know you as the owner of a humble ice cream shop. Little do they know, at night you are none other than the renowned agent Gogo 31!
You have trained for more than 10,000 hours—not as much as the Great Spaitama, but a decent amount nonetheless—and can now easily shoot targets from far away. You can still only shoot in straight lines, unlike your archrival Isli Texon. Your bullet also stops when it hits an enemy or any other obstacle.
Excellent as you are, you take the night as an opportunity to train and improve your shooting skills even further. You turn your ice cream shop and backyard into a shooting range, setting up the targets and obstacles in different configurations.
Your training ground can be viewed as a grid of $R$ rows and $C$ columns. When shooting, you can only move along your ice cream shop, which takes up the whole of the bottommost row. The rest of the rows contain either obstacles, targets, or empty space.
For each given configuration, how many targets can you possibly hit?
The first line of the input contains a single integer $t$, the number of test cases.
Each case starts with integers $r$ and $c$, representing your training ground. Then follow $r -1$ lines with $c$ characters each. A "_#_" represents an obstacle, "_X_" represents a target, and "_._" is an empty space.
*Constraints*
$0 <= t$
$2 <= r <= 500$
$1 <= c <= 500$
The sum of ($r times c$) across all test cases per file is lower than $1000000$
For each test case, print a line indicating the number of targets that you could possibly hit.
The following illustrates the first sample input:
## Input
The first line of the input contains a single integer $t$, the number of test cases.Each case starts with integers $r$ and $c$, representing your training ground. Then follow $r -1$ lines with $c$ characters each. A "_#_" represents an obstacle, "_X_" represents a target, and "_._" is an empty space.*Constraints*$0 <= t$$2 <= r <= 500$ $1 <= c <= 500$The sum of ($r times c$) across all test cases per file is lower than $1000000$
## Output
For each test case, print a line indicating the number of targets that you could possibly hit.
[samples]
## Note
The following illustrates the first sample input:
**Definitions**
Let $ h, w \in \mathbb{Z}^+ $ denote the height and width of a grid.
Let $ G \in \{B, R, W\}^{h \times w} $ be a grid where each cell is labeled:
- $ B $: blue tile (turn right),
- $ R $: red tile (turn left),
- $ W $: white tile (move forward).
Let $ \mathcal{D} = \{N, E, S, W\} $ be the set of four cardinal directions.
Let $ \mathcal{W} $ be the set of wall segments:
- Top wall: $ \{(N, j) \mid j \in \{1, \dots, w\}\} $,
- Bottom wall: $ \{(S, j) \mid j \in \{1, \dots, w\}\} $,
- Left wall: $ \{(W, i) \mid i \in \{1, \dots, h\}\} $,
- Right wall: $ \{(E, i) \mid i \in \{1, \dots, h\}\} $.
Let $ \mathcal{S} \subseteq \mathcal{W} $ be the set of reachable wall segments starting from any tile $ (i,j) \in \{1,\dots,h\} \times \{1,\dots,w\} $ with any initial direction $ d \in \mathcal{D} $, following deterministic movement rules:
- On $ B $: turn right (clockwise) then move forward.
- On $ R $: turn left (counterclockwise) then move forward.
- On $ W $: move forward without turning.
Let $ \mathcal{S}' $ be the set of wall segments reachable when **at most one** $ W $ tile is changed to either $ B $ or $ R $.
**Constraints**
1. $ 1 \le t \le 100 $
2. $ 1 \le h, w \le 50 $
3. Grid contains only characters $ B, R, W $.
**Objective**
Compute $ \mathcal{S}' $, the set of distinct wall segments reachable under the above rules with at most one tile modification.
Output $ |\mathcal{S}'| $, followed by the elements of $ \mathcal{S}' $ sorted lexicographically: first by wall side ($ N < E < S < W $), then by index (1-based).