You are teaching a class of $N$ students. Today, during the morning prayer, all the students are standing in a line. You are given a string $s$ with length $N$; for each valid $i$, the $i$-th character of this string is 'b' if the $i$-th student in the line is a boy or 'g' if this student is a girl.
The awkwardness of this configuration of students is defined as the sum of pairwise distances between each boy and girl. The distance between the $i$-th and $j$-th student in the line is $|i - j|$. Formally, the awkwardness is ∑i=1N∑j=i+1sj≠siN(j−i).∑i=1N∑j=i+1sj≠siN(j−i).\sum\limits_{i=1}^N \, \sum\limits_{j=i+1\\ s_j \neq s_i}^N (j - i)\,.
As the teacher, it is your responsibility to reorder the students in such a way that the awkwardness of the resulting configuration is the smallest possible. You may reorder the students in the line in any way you want. Find the minimum awkwardness that can be achieved.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single string $s$.

-----Output-----
For each test case, print a single line containing one integer - the minimum possible awkwardness.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le |s| \le 10^5$
- each character of $s$ is either 'b' or 'g'
- the sum of $|s|$ over all test cases does not exceed $4 \cdot 10^6$

-----Example Input-----
3
gb
bgg
bbgg

-----Example Output-----
1
2
6

-----Explanation-----
Example case 1: The total awkwardness is $|1 - 0| = 1$, no matter how you arrange the students.
Example case 2: Initially, the awkwardness is $|1 - 0| + |2 - 0| = 1 + 2 = 3$. However, you can move the boy between the two girls, i.e. choose the configuration "gbg". Here, the awkwardness is $|1 - 0| + |2 - 1| = 1 + 1 = 2$.

Difficulty: interview

Starter code:

Solutions:
from collections import Counter 
for _ in range(int(input())):
 s = input()
 c = Counter(list(s))
 if len(c) == 1:
  print(0)
 else:
  m = min(c['b'], c['g'])
  ma = max(c['b'], c['g'])
  l = (ma - m + 1) // 2
  r = (ma - m + 1) // 2 + (ma - m + 1) % 2
  res = (l * (l + 1)) // 2
  re = res
  for i in range(1, m):
   res += 2 * l + 1
   re += res
   l += 1
  res2 = (r * (r + 1)) // 2
  re += res2
  for i in range(1, m):
   res2 += 2 * r + 1
   re += res2
   r += 1
  print(re)

for _ in range(int(input())):
 string = input()
 girls,boys = string.count('g'),string.count('b')
 arrangement = ""
 answer = 0
 if(boys > girls):
  boys, girls = girls, boys
 boys_index = []
 pos = 0
 extra_right = (girls - boys) // 2
 extra_left = girls - boys - extra_right
 arrangement += 'g'*extra_left
 pos += extra_left
 for i in range(boys):
  arrangement += 'bg'
  boys_index.append(pos)
  pos += 2
 arrangement += 'g'*extra_right
 nb = 0
 ng = 0
 for i in range(len(arrangement)):
  if(arrangement[i] == 'g'):
   answer += i*nb - i*(boys-nb)
   ng += 1
  else:
   answer += i*ng - i*(girls-ng)
   nb += 1
 
 print(answer)

# cook your dish here
# cook your dish here
try:
 T = int(input())
 for i in range (0,T):
  s = input()
  p, q = s.count("b"), s.count("g")
  d = 0
  c = q - p
  r = c // 2
  if len(s) == 0:
   print(d)
  else:
   if p == q:
    d = (q*(2*(q**2)+1))/3
   elif p>q:
    d = (q*(2*(q**2)+1))/3
    c = p - q
    r = c // 2
    d = d + (q*r*(2*q + r))
   elif q>p:
    d = (p*(2*(p**2)+1))/3
    d = d + (p*r*(2*p + r))
   if r == c / 2:
    print(int(d))
   else:
    if q<p:
     d = d + q*r + q**2
    else:
     d = d + p*r + p**2
    print(int(d))
except:
 pass


# cook your dish here
try:
 T = int(input())
 for i in range (0,T):
  s = input()
  p, q = s.count("b"), s.count("g")
  d = 0
  c = q - p
  r = c // 2
  if len(s) == 0:
   print(d)
  else:
   if p == q:
    d = (q*(2*(q**2)+1))/3
   elif p>q:
    d = (q*(2*(q**2)+1))/3
    c = p - q
    r = c // 2
    d = d + (q*r*(2*q + r))
   elif q>p:
    d = (p*(2*(p**2)+1))/3
    d = d + (p*r*(2*p + r))
   if r == c / 2:
    print(int(d))
   else:
    if q<p:
     d = d + q*r + q**2
    else:
     d = d + p*r + p**2
    print(int(d))
except:
 pass


from collections import Counter 
for _ in range(int(input())):
 s = input()
 c = Counter(list(s))
 if len(c) == 1:
  print(0)
 else:
  m = min(c['b'], c['g'])
  ma = max(c['b'], c['g'])
  l = (ma - m + 1) // 2
  r = (ma - m + 1) // 2 + (ma - m + 1) % 2
  res = (l * (l + 1)) // 2
  re = res
  for i in range(1, m):
   res += 2 * l + 1
   re += res
   l += 1
  res2 = (r * (r + 1)) // 2
  re += res2
  for i in range(1, m):
   res2 += 2 * r + 1
   re += res2
   r += 1
  print(re)

from collections import Counter 
for _ in range(int(input())):
 s = input()
 c = Counter(list(s))
 if len(c) == 1:
  print(0)
 else:
  m = min(c['b'], c['g'])
  ma = max(c['b'], c['g'])
  l = (ma - m + 1) // 2
  r = (ma - m + 1) // 2 + (ma - m + 1) % 2
  res = (l * (l + 1)) // 2
  re = res
  for i in range(1, m):
   res += 2 * l + 1
   re += res
   l += 1
  res2 = (r * (r + 1)) // 2
  re += res2
  for i in range(1, m):
   res2 += 2 * r + 1
   re += res2
   r += 1
  print(re)

def ans(x,g):
 return x*g*g+((x*(x-1))//2)*g 
 
for _ in range(int(input())):
 s=list(input())
 g,b=s.count('g'),s.count('b')
 if g>b:
  g,b=b,g 
 #print(b,g)
 n=(g-1)
 co=0
 co+=((n)*(n+1)*(2*n+1))//3 
 #print(co)
 b=b-(g-1) 
 #print(b,g)
 if b%2==0:
  x=b//2
  co+=2*ans(x,g)
 else:
  x,y=b//2,b//2+1 
  co+=ans(x,g)+ans(y,g)
 if co<=0:print(0)
 else:print(co)


from itertools import permutations as p
t=int(input())
for _ in range(t):
 s=input()
 
 a=s.count('b')
 b=s.count('g')
 if a==0 or b==0:
  print(0)
  continue
 if a<=b:
  k=b-a+1
  x=k//2
  y=k//2
  if k%2:
   x+=1
  s='g'*x
  for i in range(a-1):
   s+='b'
   s+='g'
  s+='b'
  s+='g'*y

 else:
  temp=a
  a=b
  b=temp
  
  k=b-a+1
  x=k//2
  y=k//2
  if k%2:
   x+=1
  s='g'*x
  for i in range(a-1):
   s+='b'
   s+='g'
  s+='b'
  s+='g'*y

 ans=0
 n=len(s)
 g=0
 b=0
 countg=0
 countb=0
 for i in range(n-1,-1,-1):
  if s[i]=='g':
   ans+=b-i*countb
   g+=i
   countg+=1
  else:
   ans+=g-i*countg
   b+=i
   countb+=1
 print(ans)