Time Limit: 4 Seconds
Memory Limit: 65536 KB
Today, Bob wants to play a game on a chessboard of 1*n.
At first, n chessmen, painted in either White or Black, are placed on the chessboard. Every time, Bob can choose a chessman. If the left chessman and the right chessman of the chosen one(ignore the blank cause by previous removing) are of the same color, Bob can remove the two chessmen(except the chessman he choose) from the chessboard and get two points.
For example, in the following picture, if Bob choose the black chessman in the third cell, he can remove the two white chessmen and get two points. But the chessman he choose is still at the chessboard.
With different ways of choosing, Bob can get different points. Now, Bob wants to get as much points as possible. Can you tell him the most points he can get.
The first line of input is a integer T, the number of games Bob plays. For each game he plays, the first line is the length of the chessboard n(n<=200) and the second line is a string of 'B' and 'W' which represent the color of the chessmen.
For the first game, Bob can first choose the white chessman in the second cell and remove the chessmen in the first and third cell, the chessboard become #W#BW. Then, he can choose the black chessman in the forth cell and remove the two white chessman.