Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3917
Colors of Cards

Time Limit: 1 Second      Memory Limit: 65536 KB

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.


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.


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


Sample Output


Author: XIE, Cihui
Source: ZOJ Monthly, February 2016
Submit    Status