Draughts

Time limit2sMemory limit128 MB

Summary
Find the most dark pieces one light piece can capture in a single chain of diagonal jumps on a 10x10 draughts board.
Level

Medium4 of 10

Topics
Backtracking, DFS, Simulation
Solved
No attempts yet

Problem

Draughts, also called checkers, is a game for two players who sit on opposite sides of a 10×1010 \times 10 board. The squares are painted black and white like a chessboard. One player moves the dark pieces and the other moves the light pieces. Pieces stand only on black squares. The players move alternately, each moving one of his own pieces.

The most interesting kind of move is a capture. If a diagonally adjacent square holds an opponent's piece and the square immediately beyond it is empty, that piece may be captured by jumping over it and landing on the empty square. A captured piece is removed from the board. Several captures may be made in a row within one move, as long as a single piece makes all of them. A capture may be made by a forward jump or by a backward jump.

You are given a draughts position. It is the light player's turn. Compute the maximal possible number of dark pieces he can capture in his next move.

Input

The first line contains the number of test cases TT. The test cases follow.

Each test case starts with an empty line. The following 10 lines of 10 characters each describe the board squares. # is an empty black square and . is a white square. W is a square with a light piece and B is a square with a dark piece.

Output

For each test case print a single line with the maximal possible number of captures. If no capture is possible (for example, the board holds no light piece), print 0.

Examples1

  1. Example 1

    Input
    2

.#.#.#.#.#
#.#.#.#.#.
.#.#.B.#.#
#.#.#.#.#.
.#.#.B.#.#
#.#.W.#.#.
.#.#.#.#.#
#.#.#.B.#.
.#.#.#.#.#
#.#.#.#.#.

.#.#.#.#.#
#.#.#.#.#.
.#.#.B.#.#
#.B.#.B.#.
.#.#.B.#.#
#.B.W.#.#.
.#.B.B.#.#
#.#.#.#.#.
.#.B.B.#.#
#.#.#.#.#.
    Expected output
    2
4