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: interview

Starter code:

Solutions:
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)
 else:
  if 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() 


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))#Impossible condition
 else:
  if 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)
    #After genarating list pass it to the function
   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:
   #Start with boys
   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)
    #After genarating list pass it to the function
   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() 


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')
 else:
  if 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)))

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()
 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)

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))

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 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))

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
 beven = 0
 geven = 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
    beven+=1
   elif((idx%2 and s[i]=='G') or (i%2 and char=='G')):
    gans += abs(i-idx)**c
    geven+=1
   stack.pop(len(stack)-1)
  else:
   stack.append((i,s[i]))
  #print(stack,end='  ')
 """
    if(len(stack)>0):
     idx,char = stack[len(stack)-1]
     if(char=='G'):
      geven+=1
     else:
      beven+=1
    print("geven =",geven,"beven =",beven,end=' ')
    """
 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))


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
 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))


"""
arrange string in a form that no two 'B' or two 'G' come together, if can't     return -1
cost = |i-j|**t
minimize cost
"""

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)
    else:
     if(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=[]
 #print(eqcost,cost)
 if(bcount==gcount):
  return min(eqcost,cost)
 return eqcost 
   
 


for t in range(int(input())):
 c = int(input())
 s = input()
 print(solve(s,c))


"""
arrange string in a form that no two 'B' or two 'G' come together, if can't     return -1
cost = |i-j|**t
minimize cost
"""

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)
    else:
     if(len(B)>0):
      t = B.pop(0)
      cost+=abs(t-i)**c
     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=[]
 #print(eqcost,cost)
 if(bcount==gcount):
  return min(eqcost,cost)
 return eqcost 
   
 


for t in range(int(input())):
 c = int(input())
 s = input()
 print(solve(s,c))