import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Praveen
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		DEVCLASS solver = new DEVCLASS();
		int testCount = Integer.parseInt(in.next());
		for (int i = 1; i <= testCount; i++)
			solver.solve(i, in, out);
		out.close();
	}
}

class DEVCLASS {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int type = in.nextInt();
        String s = in.next();
        if (type < 0 || type > 2) {
            throw new RuntimeException();
        }
        if (s.length() < 1 || s.length() > 100000) {
            throw new RuntimeException();
        }
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != 'B' && s.charAt(i) != 'G') {
                throw new RuntimeException();
            }
        }
        int cntBoys = 0, cntGirls = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'B') {
                cntBoys++;
            } else {
                cntGirls++;
            }
        }
		// if cntBoys and cntGirls differ by more than 1, then it is impossible to convert them into a desired format.
        if (Math.abs(cntBoys - cntGirls) > 1) {
            out.println(-1);
        } else {
            StringBuilder t = new StringBuilder();
            char last = 'B';
            for (int i = 0; i < s.length(); i++) {
                t.append(last);
                if (last == 'B') {
                    last = 'G';
                } else {
                    last = 'B';
                }
            }
			// check answer with BRBR..
            long ans = s.length();
            if (valid(t.toString(), cntBoys, cntGirls)) {
                ans = Math.min(ans, solve(s, t.toString(), type));
            }
            last = 'G';
            StringBuilder t1 = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                t1.append(last);
                if (last == 'B') {
                    last = 'G';
                } else {
                    last = 'B';
                }
            }
			// check answer with RBRB...
            if (valid(t1.toString(), cntBoys, cntGirls)) {
                ans = Math.min(ans, solve(s, t1.toString(), type));
            }
            out.println(ans);
        }
    }
	
	// checks whether it is possible to convert s to a valid string or not.
	// For finding out possibility of converting s to a valid string t, you just need to check whether the count of B's and G's in s and t match or not
    private boolean valid(String s, int cntBoys, int cntGirls) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'B') {
                cntBoys--;
            } else {
                cntGirls--;
            }
        }
        if (cntBoys == 0 && cntGirls == 0){
            return true;
        } else {
            return false;
        }
    }
	
	// create the array a as mentioned in the editorial.
    private long solve(String s, String t, int type) {
        long [] a = new long[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (s.charAt(i) == 'B') {
                    a[i] = 1;
                } else {
                    a[i] = -1;
                }
            }  else {
                a[i] = 0;
            }
        }
        return solve(a, type);
    }

	// solve according to the cases according to types.
    private long solve(long[] a, int type) {
        if (a.length == 0) {
            return 0;
        }
        long ans = 0;
        int misMatch = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] != 0) {
                misMatch++;
            }
        }
        if (misMatch % 2 != 0) {
            throw new RuntimeException();
        }
		// for type = 0, Cost of each operation is 1. You just need to find out number of position i, such that s[i] != t[i] (Let us call it that number x).
		// As you can swap any two positions i and j by just paying cost equal to 1. So overall you need x / 2 operations in the best case.
        if (type == 0) {
            ans = misMatch / 2;
        } else {
            // This problem is a simplified version of problem http://www.codechef.com/problems/PRLADDU.
			for (int i = 0; i + 1 < a.length; i++) {
                a[i + 1] += a[i];
                ans += Math.abs(a[i]);
            }
            if (a[a.length - 1] != 0) {
                throw new RuntimeException();
            }
        }
        return ans;
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}