In the game of Go, a player places stones on a grid. A stone or group of stones is surrounded if it has no liberties (adjacent empty spaces). The goal is to capture a group of stones by surrounding them completely with your own stones.
In this problem, you are given a board representing a Go game, where each cell can either contain a stone ( 'X' ) or be empty ( 'O' ). A group of stones is considered captured if all the stones in that group are completely surrounded by the opponent’s stones and none of the stones in that group are on the edge of the board.
Given a board, you need to capture all the groups of stones ( 'O' ) that are surrounded by the opponent’s stones ( 'X' ) and replace them with 'X' . Output the number of O stones left on the board after capturing all the groups of stones
Rules:
- A group of
'O'stones is captured if it is surrounded by'X'stones. - Stones on the edge of the board are not captured, as they are not fully surrounded.
- The goal is to replace all
'O'stones that are surrounded by'X'with'X', while leaving the ‘O’ stones that are on the edge or connected to an edge intact.
Input Format
- The first line contains an integer
tdenoting the number of test cases. - For each test case:
- The first line contains two integers
mandndenoting the number of rows and columns of the board. - The next
mlines contain a string of lengthnrepresenting the board. - Each string consists of characters
'X'or'O'.
- The first line contains two integers
Constraints
- 1≤t≤101≤t≤10
- 1≤m,n≤10001≤m,n≤1000
Output Format
For each test case, output the number of O stones left on the board after capturing all the groups of stones.
Example
Sample Input
1 4 4 XXXX XOOX XXOX XOXX
Output
1
Explanation
The O s in the middle are surrounded by X s and can be captured. However, the O on the edge cannot be captured.
After capturing the stones, the board will look like:
XXXX XXXX XXXX XOXX