Devu is a class teacher of a class of n students. One day, in the morning prayer of the school, all the students of his class were standing in a line. You are given information of their arrangement by a string s. The string s consists of only letters 'B' and 'G', where 'B' represents a boy and 'G' represents a girl.
Devu wants inter-gender interaction among his class should to be maximum. So he does not like seeing two or more boys/girls standing nearby (i.e. continuous) in the line. e.g. he does not like the arrangements BBG and GBB, but he likes BG, GBG etc.
Now by seeing the initial arrangement s of students, Devu may get furious and now he wants to change this arrangement into a likable arrangement. For achieving that, he can swap positions of any two students (not necessary continuous). Let the cost of swapping people from position i with position j (i ≠ j) be c(i, j). You are provided an integer variable type, then the cost of the the swap will be defined by c(i, j) = |j − i|type.

Please help Devu in finding minimum cost of swaps needed to convert the current arrangement into a likable one.

-----Input-----
The first line of input contains an integer T, denoting the number of test cases. Then T test cases are follow.
The first line of each test case contains an integer type, denoting the type of the cost function. Then the next line contains string s of length n, denoting the initial arrangement s of students.
Note that the integer n is not given explicitly in input.

-----Output-----
For each test case, print a single line containing the answer of the test case, that is, the minimum cost to convert the current arrangement into a likable one. If it is not possible to convert the current arrangement into a likable one, then print -1 instead of the minimum cost.

-----Constraints and Subtasks-----Subtask 1: 25 points
- 1 ≤ T ≤ 105
- 1 ≤ n ≤ 105
- type = 0
- Sum of n over all the test cases in one test file does not exceed 106. 
Subtask 2: 25 points
- 1 ≤ T ≤ 105
- 1 ≤ n ≤ 105
- type = 1
- Sum of n over all the test cases in one test file does not exceed 106. 
Subtask 3: 25 points
- 1 ≤ T ≤ 105
- 1 ≤ n ≤ 105
- type = 2
- Sum of n over all the test cases in one test file does not exceed 106. 
Subtask 4: 25 points
- 1 ≤ T ≤ 102
- 1 ≤ n ≤ 103
- type can be 0, 1 or 2, that is type ∈ {0, 1, 2}.

-----Example-----
Input:
8
0
BB
0
BG
0
BBGG
1
BGG
1
BGGB
1
BBBGG
2
BBGG
2
BGB

Output:
-1
0
1
1
1
3
1
0

-----Explanation-----
Note type of the first 3 test cases is 0. So c(i, j) = 1. Hence we just have to count minimum number of swaps needed.
Example case 1. There is no way to make sure that both the boys does not stand nearby. So answer is -1.
Example case 2. Arrangement is already valid. No swap is needed. So answer is 0.
Example case 3. Swap boy at position 1 with girl at position 2. After swap the arrangement will be BGBG which is a valid arrangement. So answer is 1.
Now type of the next 3 test cases is 1. So c(i, j) = |j − i|, that is, the absolute value of the difference between i and j.
Example case 4. Swap boy at position 0 with girl at position 1. After swap the arrangement will be GBG which is a valid arrangement. So answer is |1 - 0| = 1.
Example case 5. Swap boy at position 0 with girl at position 1. After swap the arrangement will be GBGB which is a valid arrangement. So answer is |1 - 0| = 1.
Example case 6. Swap boy at position 1 with girl at position 4. After swap the arrangement will be BGBGB which is a valid arrangement. So answer is |4 - 1| = 3.
Then type of the last 2 test cases is 2. So c(i, j) = (j − i)2
Example case 7. Swap boy at position 1 with girl at position 2. After swap the arrangement will be BGBG which is a valid arrangement. So answer is (2 - 1)2 = 1.
Example case 8. Arrangement is already valid. No swap is needed. So answer is 0.

Difficulty: HARD
Tags: String algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
from collections import deque
for _ in range(int(input())):
	typ = int(input())
	s = input()
	b = g = 0
	n = len(s)
	for i in range(n):
		if s[i] == 'B':
			b += 1
		else:
			g += 1
	if b != n // 2 and g != n // 2:
		print('-1')
		continue
	cost = 0
	swap = deque()
	swapletter = ''
	if b <= g:
		for i in range(n):
			if i % 2:
				if s[i] != 'B':
					if swapletter == 'B':
						x = swap.popleft()
						cost += (i - x) ** min(1, typ)
						if len(swap) == 0:
							swapletter = ''
					else:
						if swapletter == '':
							swapletter = 'G'
						swap.append(i)
			elif s[i] != 'G':
				if swapletter == 'G':
					x = swap.popleft()
					cost += (i - x) ** min(1, typ)
					if len(swap) == 0:
						swapletter = ''
				else:
					if swapletter == '':
						swapletter = 'B'
					swap.append(i)
	else:
		cost = float('inf')
	if g <= b:
		cost2 = 0
		swap = deque()
		swapletter = ''
		for i in range(n):
			if i % 2:
				if s[i] != 'G':
					if swapletter == 'G':
						x = swap.popleft()
						cost2 += (i - x) ** min(1, typ)
						if len(swap) == 0:
							swapletter = ''
					else:
						if swapletter == '':
							swapletter = 'B'
						swap.append(i)
			elif s[i] != 'B':
				if swapletter == 'B':
					x = swap.popleft()
					cost2 += (i - x) ** min(1, typ)
					if len(swap) == 0:
						swapletter = ''
				else:
					if swapletter == '':
						swapletter = 'G'
					swap.append(i)
	else:
		cost2 = float('inf')
	print(min(cost, cost2))


t = int(input())
for test in range(t):
	(k, s, ans) = (int(input()), input(), 0)
	(cnt, odd, even, even_cnt) = ([0, 0], [0, 0], [0, 0], [0, 0])
	for (i, ch) in enumerate(s):
		index = 0 if ch == 'B' else 1
		odd[index] += abs(i - cnt[index] * 2)
		even[index] += abs(i - cnt[index] * 2 - 1)
		cnt[index] += 1
		even_cnt[index] += int(i % 2)
	if cnt[0] == cnt[1]:
		ans = min(even_cnt[0], cnt[0] - even_cnt[0]) if k == 0 else min(odd[0], even[0])
	elif cnt[0] == cnt[1] - 1:
		ans = even[0] if k else even_cnt[1]
	elif cnt[0] == cnt[1] + 1:
		ans = even[1] if k else even_cnt[0]
	else:
		ans = -1
	print(ans)


def actual_generator(a, N, start):
	result = []
	if a == 'B':
		result = ['B', 'G'] * (N // 2)
		result.append('B')
	elif a == 'G':
		result = ['G', 'B'] * (N // 2)
		result.append('G')
	elif start == 'B':
		result = ['B', 'G'] * (N // 2)
	elif start == 'G':
		result = ['G', 'B'] * (N // 2)
	return result
for _ in range(int(input())):
	typ = int(input())
	s = input()
	N = len(s)
	array = [s[i] for i in range(N)]
	countG = array.count('G')
	countB = array.count('B')
	if abs(countG - countB) > 1:
		print(-1)
	else:
		defectB = []
		defectG = []
		if countG == countB:
			actual1 = actual_generator('X', N, 'B')
			actual2 = actual_generator('X', N, 'G')
			defect1B = []
			defect1G = []
			defect2B = []
			defect2G = []
			for i in range(N):
				if actual1[i] != array[i] and actual1[i] == 'B':
					defect1B.append(i)
				elif actual1[i] != array[i] and actual1[i] == 'G':
					defect1G.append(i)
			for i in range(N):
				if actual2[i] != array[i] and actual2[i] == 'B':
					defect2B.append(i)
				elif actual2[i] != array[i] and actual2[i] == 'G':
					defect2G.append(i)
			if len(defect1B) > len(defect2B):
				defectG = defect2G
				defectB = defect2B
			else:
				defectG = defect1G
				defectB = defect1B
		elif countG > countB:
			actual = actual_generator('G', N, 'X')
			defectB = []
			defectG = []
			for i in range(N):
				if actual[i] != array[i] and actual[i] == 'B':
					defectB.append(i)
				elif actual[i] != array[i] and actual[i] == 'G':
					defectG.append(i)
		elif countB > countG:
			actual = actual_generator('B', N, 'X')
			defectB = []
			defectG = []
			for i in range(N):
				if actual[i] != array[i] and actual[i] == 'B':
					defectB.append(i)
				elif actual[i] != array[i] and actual[i] == 'G':
					defectG.append(i)
		if typ == 0:
			print(len(defectB))
		elif typ == 1:
			print(abs(sum(defectG) - sum(defectB)))


def cost(s, start, l, k):
	s1 = [start for i in range(l)]
	flag = start
	count = 0
	if start == 'B':
		flag = 'G'
	else:
		flag = 'B'
	for i in range(1, l, 2):
		s1[i] = flag
	b = []
	g = []
	res = 0
	for i in range(0, l):
		if s1[i] == 'B' and s1[i] != s[i]:
			b.append(i)
		elif s1[i] == 'G' and s1[i] != s[i]:
			g.append(i)
	if k == 0:
		return len(b)
	for i in range(len(b)):
		res += abs(g[i] - b[i])
	return res
import math
t = int(input())
for _ in range(t):
	cost_type = int(input())
	s = input()
	n = len(s)
	boy = s.count('B')
	girl = s.count('G')
	if abs(girl - boy) > 1:
		print('-1')
		continue
	elif boy > girl:
		start = 'B'
		res = cost(s, start, n, cost_type)
	elif girl > boy:
		start = 'G'
		res = cost(s, start, n, cost_type)
	elif boy == girl:
		start = 'G'
		res1 = cost(s, start, n, cost_type)
		start = 'B'
		res2 = cost(s, start, n, cost_type)
		res = min(res1, res2)
	print(res)


L = ['B', 'G']
nextBG = [[], []]

def swaps(letter, S, Type):
	ptr = [0, 0]
	cost = 0
	constant = [False if L[(i + letter) % 2] != S[i] else True for i in range(len(S))]
	for i in range(len(S)):
		while constant[nextBG[letter][ptr[letter]]] and ptr[letter] + 1 < len(nextBG[letter]):
			ptr[letter] += 1
		if nextBG[letter][ptr[letter]] < i and ptr[letter] + 1 < len(nextBG[letter]):
			ptr[letter] += 1
		if L[letter] != S[i]:
			cost += pow(nextBG[letter][ptr[letter]] - i, 1 if Type else 0)
			(S[i], S[nextBG[letter][ptr[letter]]]) = (S[nextBG[letter][ptr[letter]]], S[i])
			if ptr[letter] + 1 < len(nextBG[letter]):
				ptr[letter] += 1
		letter = (letter + 1) % 2
	return cost
for _ in range(int(input())):
	Type = int(input())
	S = input()
	nextBG[1] = [i for i in range(len(S)) if S[i] == 'G']
	nextBG[0] = [i for i in range(len(S)) if S[i] == 'B']
	if len(nextBG[0]) - len(nextBG[1]) == 1:
		print(swaps(0, list(S), Type))
	elif len(nextBG[1]) - len(nextBG[0]) == 1:
		print(swaps(1, list(S), Type))
	elif len(nextBG[0]) == len(nextBG[1]):
		print(min(swaps(0, list(S), Type), swaps(1, list(S), Type)))
	else:
		print(-1)


def outOfIndex(boys, girls, COST):
	if COST == 0:
		return len(boys)
	else:
		total_cost = [abs(x - y) for (x, y) in zip(boys, girls)]
		total_cost = sum(total_cost)
		return total_cost
for _ in range(int(input())):
	COST = int(input())
	queue = input()
	B = queue.count('B')
	G = queue.count('G')
	boys = []
	girls = []
	if abs(B - G) > 1:
		print(-1)
	elif B > G:
		for c in range(len(queue)):
			if c % 2 != 0 and queue[c] == 'B':
				boys.append(c)
			if c % 2 == 0 and queue[c] == 'G':
				girls.append(c)
		print(outOfIndex(boys, girls, COST))
		boys.clear()
		girls.clear()
	elif B < G:
		for c in range(len(queue)):
			if c % 2 != 0 and queue[c] == 'G':
				girls.append(c)
			if c % 2 == 0 and queue[c] == 'B':
				boys.append(c)
		print(outOfIndex(boys, girls, COST))
		boys.clear()
		girls.clear()
	else:
		for c in range(len(queue)):
			if c % 2 != 0 and queue[c] == 'B':
				boys.append(c)
			if c % 2 == 0 and queue[c] == 'G':
				girls.append(c)
		attempt1 = outOfIndex(boys, girls, COST)
		boys.clear()
		girls.clear()
		for c in range(len(queue)):
			if c % 2 != 0 and queue[c] == 'G':
				girls.append(c)
			if c % 2 == 0 and queue[c] == 'B':
				boys.append(c)
		attempt2 = outOfIndex(boys, girls, COST)
		print(min(attempt1, attempt2))
		boys.clear()
		girls.clear()


for _ in range(int(input())):
	t = int(input())
	s = input()
	b = []
	a = []
	c = 0
	lb = 0
	la = 0
	r = []
	ls = len(s)
	for i in s:
		c += 1
		if i == 'B':
			lb += 1
		else:
			la += 1
	if la - lb == 0 or abs(la - lb) == 1:
		if la < lb:
			for i in range(ls):
				if i % 2 == 1 and s[i] == 'B':
					b.append(i)
				if i % 2 == 0 and s[i] == 'G':
					a.append(i)
		elif la > lb:
			for i in range(ls):
				if i % 2 == 0 and s[i] == 'B':
					b.append(i)
				if i % 2 == 1 and s[i] == 'G':
					a.append(i)
		cs = 0
		sw = 0
		for i in range(len(a)):
			cs += abs(a[i] - b[i])
		if t == 0:
			cs = len(a)
		if la == lb:
			for i in range(len(s)):
				if i % 2 == 0 and s[i] == 'B':
					b.append(i)
				if i % 2 == 1 and s[i] == 'G':
					a.append(i)
			cs = 0
			sw = 0
			for i in range(len(a)):
				cs += abs(a[i] - b[i])
			if t == 0:
				cs = len(a)
			x = cs
			b = []
			a = []
			for i in range(len(s)):
				if i % 2 == 1 and s[i] == 'B':
					b.append(i)
				if i % 2 == 0 and s[i] == 'G':
					a.append(i)
			cs = 0
			sw = 0
			for i in range(len(a)):
				if i < len(b):
					cs += abs(a[i] - b[i])
			if t == 0:
				cs = len(a)
			cs = min(x, cs)
		print(cs)
	else:
		print(-1)


for _ in range(int(input())):
	t = int(input())
	s = input()
	n = len(s)
	b = 0
	for i in s:
		if i == 'B':
			b += 1
	g = n - b
	if abs(b - g) > 1:
		print('-1')
	elif b == 1 and g == 1:
		print('0')
	elif b > g:
		BG = 'BG' * (n // 2)
		if n & 1:
			BG += 'B'
		(B, G) = ([], [])
		for i in range(n):
			if s[i] != BG[i]:
				if s[i] == 'B':
					B.append(i)
				else:
					G.append(i)
		if t == 0:
			print(len(B))
		else:
			print(sum([abs(B[i] - G[i]) for i in range(len(B))]))
	elif b < g:
		BG = 'GB' * (n // 2)
		if n & 1:
			BG += 'G'
		(B, G) = ([], [])
		for i in range(n):
			if s[i] != BG[i]:
				if s[i] == 'B':
					B.append(i)
				else:
					G.append(i)
		if t == 0:
			print(len(B))
		else:
			print(sum([abs(B[i] - G[i]) for i in range(len(B))]))
	else:
		BG = 'GB' * (n // 2)
		if n & 1:
			BG += 'G'
		(B, G) = ([], [])
		for i in range(n):
			if s[i] != BG[i]:
				if s[i] == 'B':
					B.append(i)
				else:
					G.append(i)
		if t == 0:
			v1 = len(B)
		else:
			v1 = sum([abs(B[i] - G[i]) for i in range(len(B))])
		BG = 'BG' * (n // 2)
		if n & 1:
			BG += 'B'
		(B, G) = ([], [])
		for i in range(n):
			if s[i] != BG[i]:
				if s[i] == 'B':
					B.append(i)
				else:
					G.append(i)
		if t == 0:
			v2 = len(B)
		else:
			v2 = sum([abs(B[i] - G[i]) for i in range(len(B))])
		print(min(v1, v2))


def compute(s, c):
	bcount = s.count('B')
	gcount = s.count('G')
	if abs(bcount - gcount) > 1:
		return -1
	stack = [(0, s[0])]
	bans = 0
	gans = 0
	if c != 0:
		c = 1
	for i in range(1, len(s)):
		if len(stack) > 0 and stack[len(stack) - 1][1] != s[i]:
			(idx, char) = stack[len(stack) - 1]
			if idx % 2 and s[i] == 'B' or (i % 2 and char == 'B'):
				bans += abs(i - idx) ** c
			elif idx % 2 and s[i] == 'G' or (i % 2 and char == 'G'):
				gans += abs(i - idx) ** c
			stack.pop(len(stack) - 1)
		else:
			stack.append((i, s[i]))
	if gcount == bcount:
		return min(bans, gans)
	elif gcount > bcount:
		return bans
	return gans
for t in range(int(input())):
	c = int(input())
	print(compute(input(), c))


t = int(input())
for _ in range(t):
	type = int(input())
	global c
	c = 0
	c1 = 0
	c2 = 0
	s = input()
	b1 = []
	g1 = []
	b2 = []
	g2 = []
	b = s.count('B')
	g = s.count('G')
	if abs(g - b) > 1:
		print('-1')
	else:
		if b > g:
			for k in range(len(s)):
				if k % 2 == 0 and s[k] != 'B':
					b1.append(k)
				if k % 2 != 0 and s[k] != 'G':
					g1.append(k)
			for i in range(len(b1)):
				sb = abs(g1[i] - b1[i])
				if type != 2:
					c = c + sb ** type
				else:
					c = c + sb
		if g > b:
			for k in range(len(s)):
				if k % 2 == 0 and s[k] != 'G':
					g1.append(k)
				if k % 2 != 0 and s[k] != 'B':
					b1.append(k)
			for i in range(len(g1)):
				sb = abs(g1[i] - b1[i])
				if type != 2:
					c = c + sb ** type
				else:
					c = c + sb
		if g == b:
			if True:
				for k in range(len(s)):
					if k % 2 == 0 and s[k] != 'B':
						b1.append(k)
					if k % 2 != 0 and s[k] != 'G':
						g1.append(k)
				for i in range(len(b1)):
					sb = abs(g1[i] - b1[i])
					if type != 2:
						c1 = c1 + sb ** type
					else:
						c1 = c1 + sb
			if True:
				for k in range(len(s)):
					if k % 2 == 0 and s[k] != 'G':
						g2.append(k)
					if k % 2 != 0 and s[k] != 'B':
						b2.append(k)
				for i in range(len(g2)):
					sb = abs(g2[i] - b2[i])
					if type != 2:
						c2 = c2 + sb ** type
					else:
						c2 = c2 + sb
			if c1 > c2:
				c = c2
			else:
				c = c1
		print(int(c))


import math

def cost(s, c, l):
	s1 = [c for i in range(0, l)]
	c1 = c
	if c == 'B':
		c1 = 'G'
	else:
		c1 = 'B'
	for i in range(1, l, 2):
		s1[i] = c1
	a = []
	b = []
	res = 0
	for i in range(0, l):
		if s1[i] == 'B' and s1[i] != s[i]:
			a.append(i)
		elif s1[i] == 'G' and s1[i] != s[i]:
			b.append(i)
	if k == 0:
		return len(a)
	for i in range(0, len(a)):
		res = res + abs(a[i] - b[i])
	return res
t = int(input())
for I in range(0, t):
	k = int(input())
	s = input()
	l = len(s)
	cg = 0
	cb = 0
	for i in range(0, l):
		if s[i] == 'G':
			cg = cg + 1
		else:
			cb = cb + 1
	res = 0
	if abs(cg - cb) > 1:
		print('-1')
		continue
	elif cb > cg:
		c = 'B'
		res = cost(s, c, l)
	elif cg > cb:
		c = 'G'
		res = cost(s, c, l)
	else:
		c = 'G'
		s1 = cost(s, c, l)
		c = 'B'
		s2 = cost(s, c, l)
		res = min(s1, s2)
	print(res)


__author__ = 'sanjay'

def min_count(string, tp):
	(B, G) = ([], [])
	for i in range(len(string)):
		if i % 2 != 0:
			G.append('B')
			B.append('G')
		else:
			G.append('G')
			B.append('B')
	count = string.count('B') - string.count('G')
	if abs(count) > 1:
		return -1
	elif count > 0:
		(b, g) = ([], [])
		for i in range(len(string)):
			if string[i] != B[i]:
				if i % 2 != 0:
					b.append(i)
				else:
					g.append(i)
		ans = 0
		for i in range(len(b)):
			ans += pow(abs(b[i] - g[i]), tp)
		return ans
	elif count < 0:
		(b, g) = ([], [])
		for i in range(len(string)):
			if string[i] != G[i]:
				if i % 2 != 0:
					g.append(i)
				else:
					b.append(i)
		ans = 0
		for i in range(len(b)):
			ans += pow(abs(b[i] - g[i]), tp)
		return ans
	elif count == 0:
		(b, g) = ([], [])
		for i in range(len(string)):
			if string[i] != G[i]:
				if i % 2 != 0:
					g.append(i)
				else:
					b.append(i)
		ans1 = 0
		for i in range(len(b)):
			ans1 += pow(abs(b[i] - g[i]), tp)
		(b, g) = ([], [])
		for i in range(len(string)):
			if string[i] != B[i]:
				if i % 2 != 0:
					b.append(i)
				else:
					g.append(i)
		ans2 = 0
		for i in range(len(b)):
			ans2 += pow(abs(b[i] - g[i]), tp)
		return min(ans1, ans2)
test = int(input())
while test:
	test -= 1
	tp = int(input())
	if tp == 2:
		tp = 1
	string = input()
	print(min_count(string, tp))


t = int(input())
for i in range(1, t + 1):
	type1 = int(input())
	s = input()
	count1 = count2 = 0
	countB = countG = 0
	if type1 == 0:
		for j in range(0, len(s)):
			if s[j] == 'B':
				countB += 1
			else:
				countG += 1
			if j % 2 == 0:
				if s[j] != 'B':
					count1 += 1
				else:
					count2 += 1
			elif s[j] != 'G':
				count1 += 1
			else:
				count2 += 1
		if abs(countB - countG) <= 1:
			if count1 == 0 or count2 == 0:
				print('0')
			elif len(s) % 2 == 1:
				if countB > countG:
					print(count1 // 2)
				else:
					print(count2 // 2)
			else:
				print(min(count1, count2) // 2)
		else:
			print('-1')
	else:
		Bmis1 = []
		Bmis2 = []
		Gmis1 = []
		Gmis2 = []
		for j in range(0, len(s)):
			if s[j] == 'B':
				countB += 1
			else:
				countG += 1
			if j % 2 == 0:
				if s[j] != 'B':
					Gmis1.append(j)
					if Bmis1:
						count1 = count1 + abs(Gmis1.pop() - Bmis1.pop())
				else:
					Bmis2.append(j)
					if Gmis2:
						count2 = count2 + abs(Gmis2.pop() - Bmis2.pop())
			elif s[j] != 'G':
				Bmis1.append(j)
				if Gmis1:
					count1 = count1 + abs(Gmis1.pop() - Bmis1.pop())
			else:
				Gmis2.append(j)
				if Bmis2:
					count2 = count2 + abs(Gmis2.pop() - Bmis2.pop())
		if abs(countB - countG) <= 1:
			if count1 == 0 and (Bmis1 == [] and Gmis1 == []) or (count2 == 0 and (Bmis2 == [] and Gmis2 == [])):
				print('0')
			elif len(s) % 2 == 1:
				if countB > countG:
					print(count1)
				else:
					print(count2)
			else:
				print(min(count1, count2))
		else:
			print('-1')


t = int(input())
for k in range(t):
	type = int(input())
	a = input()
	str1 = 'B'
	str2 = 'G'
	b1 = []
	g1 = []
	b2 = []
	g2 = []
	for i in range(1, len(a), 1):
		if str1[i - 1] == 'B':
			str1 += 'G'
		elif str2[i - 1] == 'B':
			str2 += 'G'
		if str1[i - 1] == 'G':
			str1 += 'B'
		elif str2[i - 1] == 'G':
			str2 += 'B'
	for i in range(len(a)):
		if str1[i] != a[i] and a[i] == 'B':
			b1.append(i)
		elif str1[i] != a[i] and a[i] == 'G':
			g1.append(i)
		if str2[i] != a[i] and a[i] == 'B':
			b2.append(i)
		elif str2[i] != a[i] and a[i] == 'G':
			g2.append(i)
	cost1 = 0
	cost2 = 0
	while len(b1) > 0 and len(g1) > 0:
		no1 = b1.pop()
		no2 = g1.pop()
		if type == 0:
			cost1 += 1
		else:
			cost1 += abs(no2 - no1)
	if len(b1) != 0 or len(g1) != 0:
		cost1 = 10000000000000000000000000007
	while len(b2) > 0 and len(g2) > 0:
		no1 = b2.pop()
		no2 = g2.pop()
		if type == 0:
			cost2 += 1
		else:
			cost2 += abs(no2 - no1)
	if len(b2) > 0 or len(g2) > 0:
		cost2 = 100000000000000000000000000007
	if (len(b1) > 0 or len(g1) > 0) and (len(b2) > 0 or len(g2) > 0):
		print('-1')
		continue
	print(min(cost1, cost2))


for _ in range(int(input())):
	t = int(input())
	s = input()
	b = 0
	g = 0
	for i in s:
		if i == 'B':
			b += 1
		else:
			g += 1
	if abs(g - b) > 1:
		print('-1')
	elif g - b > 0:
		gl = []
		bl = []
		for i in range(len(s)):
			if s[i] == 'B' and i % 2 == 0:
				bl.append(i)
			elif s[i] == 'G' and i % 2 == 1:
				gl.append(i)
		c = 0
		for i in range(len(bl)):
			if t == 0:
				c += 1
			else:
				c += abs(gl[i] - bl[i])
		print(c)
	elif b - g > 0:
		gl = []
		bl = []
		for i in range(len(s)):
			if s[i] == 'B' and i % 2 == 1:
				bl.append(i)
			elif s[i] == 'G' and i % 2 == 0:
				gl.append(i)
		c = 0
		for i in range(len(bl)):
			if t == 0:
				c += 1
			else:
				c += abs(gl[i] - bl[i])
		print(c)
	else:
		gl = []
		bl = []
		for i in range(len(s)):
			if s[i] == 'B' and i % 2 == 0:
				bl.append(i)
			elif s[i] == 'G' and i % 2 == 1:
				gl.append(i)
		c1 = 0
		for i in range(len(bl)):
			if t == 0:
				c1 += 1
			else:
				c1 += abs(gl[i] - bl[i])
		gl = []
		bl = []
		for i in range(len(s)):
			if s[i] == 'B' and i % 2 == 1:
				bl.append(i)
			elif s[i] == 'G' and i % 2 == 0:
				gl.append(i)
		c2 = 0
		for i in range(len(bl)):
			if t == 0:
				c2 += 1
			else:
				c2 += abs(gl[i] - bl[i])
		if c2 < c1:
			print(c2)
		else:
			print(c1)


def sums(a, b):
	return sum([abs(a[i] - b[i]) for i in range(0, len(a))])

def cost(s, t, pt=False):
	lb = []
	lg = []
	rb = []
	rg = []
	nb = ng = 0
	for i in range(0, len(s)):
		if s[i] == 'B':
			nb += 1
			if i % 2:
				lb.append(i)
			else:
				rb.append(i)
		else:
			ng += 1
			if i % 2 == 0:
				lg.append(i)
			else:
				rg.append(i)
	if pt:
		print(s, t, nb, ng, lb, lg, rb, rg)
	if nb - ng > 1 or nb - ng < -1:
		return -1
	if nb - ng == -1 or len(rb) == 0:
		lb = rb
		lg = rg
	if pt:
		print(s, t, nb, ng, lb, lg, rb, rg)
	assert len(lb) == len(lg)
	if t == 0:
		if nb == ng:
			return min(len(lb), len(rb))
		else:
			return len(lb)
	elif len(rb) == len(rg):
		return min(sums(lb, lg), sums(rb, rg))
	else:
		return sums(lb, lg)
for i in range(int(input())):
	t = int(input())
	s = input()
	print(cost(s, t))


def solve(s, c):
	bcount = s.count('B')
	gcount = s.count('G')
	if abs(bcount - gcount) > 1:
		return -1
	B = []
	G = []
	start = 'B'
	cost = 0
	if bcount < gcount:
		start = 'G'
	iterate = 1
	temp = start
	if bcount == gcount:
		iterate = 2
	for y in range(iterate):
		for i in range(len(s)):
			if s[i] != start:
				if s[i] == 'B':
					if len(G) > 0:
						t = G.pop(0)
						cost += abs(t - i) ** c
					else:
						B.append(i)
				elif len(B) > 0:
					t = B.pop(0)
					cost += pow(abs(t - i), c, 10 ** 6)
				else:
					G.append(i)
			if start == 'B':
				start = 'G'
			else:
				start = 'B'
		if temp == 'B':
			start = 'G'
		else:
			start = 'B'
		if y == 1:
			break
		eqcost = cost
		cost = 0
		B = []
		G = []
	if bcount == gcount:
		return min(eqcost, cost)
	return eqcost
for t in range(int(input())):
	c = int(input())
	s = input()
	print(solve(s, c))


t = int(input())
while t > 0:
	k = int(input())
	s = input()
	b = s.count('B')
	g = s.count('G')
	m = []
	n = []
	c = []
	d = []
	if b == g + 1:
		s = s + 'G'
		i = 0
		while i < len(s):
			if s[i] != 'B':
				m.append(i)
			if s[i + 1] != 'G':
				n.append(i + 1)
			i = i + 2
		if k == 0:
			print(len(m))
		elif k == 1 or k == 2:
			y = 0
			for i in range(len(m)):
				y = y + abs(m[i] - n[i])
			print(y)
	elif g == b + 1:
		s = s + 'B'
		i = 0
		while i < len(s):
			if s[i] != 'G':
				n.append(i)
			if s[i + 1] != 'B':
				m.append(i + 1)
			i = i + 2
		if k == 0:
			print(len(m))
		elif k == 1 or k == 2:
			y = 0
			for i in range(len(m)):
				y = y + abs(m[i] - n[i])
			print(y)
	elif b == g:
		i = 0
		while i < len(s):
			if s[i] != 'B':
				m.append(i)
			if s[i + 1] != 'G':
				n.append(i + 1)
			i = i + 2
		i = 0
		while i < len(s):
			if s[i] != 'G':
				c.append(i)
			if s[i + 1] != 'B':
				d.append(i + 1)
			i = i + 2
		if k == 0:
			print(min(len(c), len(m)))
		elif k == 1 or k == 2:
			y = 0
			z = 0
			for i in range(len(m)):
				y = y + abs(m[i] - n[i])
			for i in range(len(c)):
				z = z + abs(c[i] - d[i])
			print(min(z, y))
	else:
		print('-1')
	t = t - 1


from collections import deque, Counter
from operator import neg
from sys import stdin
_data = iter(stdin.read().split('\n'))
input = lambda : next(_data)
cs = [lambda x: 1, lambda x: x]

def solve(a, t):
	b = tuple((1 if i % 2 == 0 else -1 for i in range(n)))
	q = deque()
	r = 0
	if t <= 1:
		c = cs[t]
		for (i, (x, y)) in enumerate(zip(a, b)):
			if x * y == -1:
				if not q or a[q[0]] == x:
					q.append(i)
				else:
					r += c(i - q.popleft())
	else:
		v = 0
		for (i, (x, y)) in enumerate(zip(a, b)):
			if not q:
				if x * y == -1:
					v = x
					q.append(i)
			elif v != x:
				r += i - q.popleft()
				if x == y:
					q.append(i)
			elif x * y == -1:
				q.append(i)
	return r
buf = []
for _ in range(int(input())):
	t = int(input())
	a = tuple((1 if c == 'B' else -1 for c in input()))
	n = len(a)
	ct = Counter(a)
	if ct[-1] == ct[1]:
		r = min(solve(a, t), solve(tuple(map(neg, a)), t))
		buf.append(str(r))
	elif ct[-1] == ct[1] + 1:
		buf.append(str(solve(tuple(map(neg, a)), t)))
	elif ct[1] == ct[-1] + 1:
		buf.append(str(solve(a, t)))
	else:
		buf.append(str(-1))
print('\n'.join(buf))