Problem E
Help Roomba Find Himself

Roomba is a healthy, adolescent robot, who loves his job. The work is simple, but rewarding: every morning Roomba sets out from his cosy docking station and follows a set path throughout his masters’ house, carefully sweeping up every dust bunny he encounters, before he returns to his docking station. Today, however, work turned into a nightmare, when a fierce neighborhood bulldog, known for his anti-robot attitudes, somehow got into Roomba’s way and pushed him out of his path. There is no thing that Roomba dislikes more than being lost, and now Roomba’s only wish is to figure out where he is, so he can get back to his job as sweeper extraordinaire. Roomba has the whole floor plan of his masters’ house comitted to memory, and he is an extraordinarily smart (although somewhat cowardly) robot. Now he wonders: if I do my very best, how many moves will I need to figure out where I am?

Roomba can tell he is in a tiled hallway that’s only one tile wide but many tiles long. He can gather clues about where in the hallway he may be by scanning the color of the tile he is currently on. All tiles in the hallway are either black or white. Because Roomba has a fear of looking like he doesn’t know what he’s doing, once he starts moving in a certain direction he can’t stop and decide to move the other way. If Roomba crosses outside of the tiles of the hallway he will instantly see that the tile color is neither black or white, and be able to deduce exactly where he is.

Input

The first line of the input consist of a single integer $T$, the number of test cases.
Each test case is given by two lines: The first line consists of an integer $L$ and a character $C$, giving, respectively, the length of the hallway where Roomba is located, and the color of the tile he finds himself on. The second line contains a string with $L$ characters, giving the layout of the entire hallway. A black tile is denoted by the character B, a white tile is denoted by the character W.

• $1 \leq T \leq 20$

• $1 \leq L \leq 2000$

Output

For each test case, output the maximum number of moves Roomba will need to determine his location with certainty, assuming he searches with an optimal strategy.

3
2 W
WB
4 W
WWWW
4 W
WWBW

0
3
1