国际跳棋(Draughts,或称 checkers)是一种由两名对手在 $10 \times 10$ 的棋盘上进行的对弈游戏。棋盘格子如同经典国际象棋棋盘一样,被涂成黑白两色。一名玩家控制深色棋子,另一名玩家控制浅色棋子。棋子只能占据黑色格子。玩家轮流走棋,每次移动自己的一枚棋子。
最有趣的走法是“吃子”:如果对角线相邻的格子里有对方的棋子,可以通过跳过它并落在其后方紧邻的空位上,从而吃掉该棋子(并将其从棋盘上移除)。在一次走棋中,如果使用同一枚棋子,允许进行多次连续跳跃吃子。向前或向后跳跃吃子都是合法的。
进行两次吃子前后的棋盘状态。
给定一个国际跳棋的局面,现在轮到浅色方走棋。请计算他在下一次走棋中最多能吃掉多少枚深色棋子。
输入格式
输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述:
每个测试用例以一个空行开始。接下来的 10 行,每行包含 10 个字符,描述棋盘上的格子。字符 # 和 . 分别表示空的黑色格子和白色格子,W 表示有浅色棋子的格子,B 表示有深色棋子的格子。
输出格式
对于每个测试用例,输出一行,包含可能的最大吃子数量。如果没有合法的走法(例如棋盘上没有浅色棋子),则直接输出 0。
样例
输入格式 1
2 .#.#.#.#.# #.#.#.#.#. .#.#.B.#.# #.#.#.#.#. .#.#.B.#.# #.#.W.#.#. .#.#.#.#.# #.#.#.B.#. .#.#.#.#.# #.#.#.#.#. .#.#.#.#.# #.#.#.#.#. .#.#.B.#.# #.B.#.B.#. .#.#.B.#.# #.B.W.#.#. .#.B.B.#.# #.#.#.#.#. .#.B.B.#.# #.#.#.#.#.
输出格式 1
2 4