Colors of Cards

Time Limit: 2 Seconds

Memory Limit: 65536 KB

Description

Alice and Bob are good friends. When they get together, any one of them always thinks up with some brilliant ideas for fun. Now Alice puts forward a new idea.

Alice will give N cards each of which is colored either black or white. And Bob has to take an arbitrary number k(1<=k<=N), then he could choose any consecutive k cards and change their colors either from black to white or from white to black each time. Notice: on the two sides Bob could choose less than k cards, but they have to be consecutive as well.

e.g. k = 2. Bob can change BWB to one of WWB, WBB, BBW, BWW.

If Bob could change all cards to white under the principle in finite steps, then he wins. When Bob take the number k, he wants to know the minimum number of steps he needs to finish the task. If he is impossible to win, he will give up immediately.

Input

The input will consist of multiple cases. The first line contains a single number T (1<=T<=100), indicating the number of cases. Then in the following T lines, each line contains a number k and a string separated by a space. The string consists of 'B's (denoting black) and 'W's (denoting white) in upper case. k * N <= 10^6.

Output

For each case, output a single line contains the minimum number of steps he has to take, if Bob is impossible to win, you should output -1.

Sample Input

2
3 BWBBWBB
2 BWB

Sample Output

3
2

Hint

None

Source

None

提交代码