Do you know Professor Saeed? He is the algorithms professor at Damascus University. Yesterday, he gave his students hard homework (he is known for being so evil) - for a given binary string $S$, they should compute the sum of $F(S, L, R)$ over all pairs of integers $(L, R)$ ($1 \le L \le R \le |S|$), where the function $F(S, L, R)$ is defined as follows:
- Create a string $U$: first, set $U = S$, and for each $i$ ($L \le i \le R$), flip the $i$-th character of $U$ (change '1' to '0' or '0' to '1').
- Then, $F(S, L, R)$ is the number of valid pairs $(i, i + 1)$ such that $U_i = U_{i+1}$.
As usual, Professor Saeed will give more points to efficient solutions. Please help the students solve this homework.

-----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 $\sum_{1 \le L \le R \le |S|} F(S, L, R)$.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le |S| \le 3 \cdot 10^6$
- the sum of $|S|$ over all test cases does not exceed $6 \cdot 10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $1 \le |S| \le 300$
- the sum of $|S|$ over all test cases does not exceed $600$
Subtask #2 (50 points): original constraints

-----Example Input-----
1
001

-----Example Output-----
6

-----Explanation-----
Example case 1:
- $L = 1, R = 1$: $U$ is "101", $F = 0$
- $L = 2, R = 2$: $U$ is "011", $F = 1$
- $L = 3, R = 3$: $U$ is "000", $F = 2$
- $L = 1, R = 2$: $U$ is "111", $F = 2$
- $L = 2, R = 3$: $U$ is "010", $F = 0$
- $L = 1, R = 3$: $U$ is "110", $F = 1$

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
 s=input()
 n=len(s)
 t=0
 ans=0
 for i in range(n-1):
  if(s[i]==s[i+1]):
   t=t+1
 x=t
 for i in range(n):
  t=x
  if(i!=0):
    if(s[i]==s[i-1]):
     t=t-1
    else:
     t=t+1
  y=t
  for j in range(i,n):
   t=y
   try:
    if(s[j]==s[j+1]):
     t=t-1
    else:
     t=t+1
   except:
    pass
   ans=ans+t
 print(ans)

for _ in range(int(input())):
 s=input()
 n=len(s)
 t=0
 ans=0
 for i in range(n-1):
  if(s[i]==s[i+1]):
   t=t+1
 x=t
 for i in range(n):
  for j in range(i,n):
   t=x
   if(i!=0):
    if(s[i]==s[i-1]):
     t=t-1
    else:
     t=t+1
   try:
    if(s[j]==s[j+1]):
     t=t-1
    else:
     t=t+1
   except:
    pass
   ans=ans+t
 print(ans)

t=int(input())
for _ in range(t):
 s=input()
 n=len(s)
 hak=0
 
 for i in range(n-1):
  if(s[i]==s[i+1]):
   hak+=1
   
 red=(hak*n*(n+1))
 red=red//2
 clu=n*n
 qwe=2*hak*n
 print(red+clu-qwe-n)

# cook your dish here
def check(s,n):
 temp=0
 haha=s[0]
 for i in range(1,n):
  if(haha==s[i]):
   temp+=1
  else:
   haha=s[i]
 return temp
for _ in range(int(input())):
 s=input()
 n=len(s)
 ans=0
 for i in range(n):
  for j in range(i,n):
   temp=s[0:i]
   for t in range(i,j+1):
    if(s[t]=='0'):
     temp+='1'
    else:
     temp+='0'
   temp+=s[j+1:]
   ans+=check(temp,n)
 print(ans)

t = int(input())
for _ in range(t):
 s = input()
 s = list(s)
 n = len(s)
 cnt = 0
 for i in range(n):
  for j in range(i,n):
   temp = s[:]
   for k in range(i,j+1):
    if(temp[k]=='1'):
     temp[k]='0'
    else:
     temp[k]='1'
   for k in range(n-1):
    if(temp[k]==temp[k+1]):
     cnt +=1
 print(cnt)
    
  


# cook your dish here
# cook your dish here

def calc(array) :
 result = 0
 for i in range (1,len(array)):
  if array[i] == array[i-1]:
   result+=1
 return result
def answer(p,q):
 result = p*(p-1)+(p*(p-3)*q)//2
 return result
for test_case in range (int(input())):
 String = input()
 sequence = []
 for i in range (len(String)) :
  sequence.append(String[i])
 q = calc(sequence)
 print(answer(len(String),q))


# cook your dish here

def calc(array) :
 result = 0
 for i in range (1,len(array)):
  if array[i] == array[i-1]:
   result+=1
 return result
def answer(p,q):
 result = p*(p-1)+(p*(p-3)*q)//2
 return result
for test_case in range (int(input())):
 String = input()
 sequence = []
 for i in range (len(String)) :
  sequence.append(String[i])
 q = calc(sequence)
 print(answer(len(String),q))

# cook your dish here
def find2(i):
 ans=0
 return (i+1)*(lenS-i-1)+i*(i+1)/2+(lenS-i-2)*(lenS-i-1)/2
for tests in range(int(input())):
 S=input()
 lenS=len(S)
 ans=0
 for i in range(lenS-1):
  if S[i]==S[i+1]:
   ans+= int(find2(i))
  else:
   ans+=lenS
 print(ans)

# cook your dish here
# the evilprofessor
t = int(input())
while t>0:
 s = input()
 length = len(s)
 ans = 0
 for l in range(length):
  for r in range(l, length):
   temp = s
   x = temp[:l]
   for i in range(l , r+1):
    if temp[i] == '0':
     x +='1'
    else:
     x +='0'
   x +=temp[r+1:]
   for k in range(len(x)-1):
    if x[k] == x[k+1]:
     ans +=1
   #print(x , ans)
 print(ans)
    
  
    
 
 t-=1


# cook your dish here
try:
 for _ in range(int(input())):
  s=input()
  size=len(s)
  m=(size*(size-1))//2
  n=size
  answer=0
  for i in range(size-1):
   if s[i]==s[i+1]:
    answer+=m
   else:
    answer+=n
  print(answer)
except Exception as e:
 print(e)

# cook your dish here
try:
 for _ in range(int(input())):
  s=input()
  size=len(s)
  m=(size*(size-1))//2
  n=size
  answer=0
  for i in range(size-1):
   if s[i]==s[i+1]:
    answer+=m
   else:
    answer+=n
  print(answer)
except Exception as e:
 print(e)

t=int(input())
for _ in range(t):
 s=list(input())
 n=len(s)
 ans=0
 c=0
 for i in range(0,n-1):
  if s[i]==s[i+1]:
   ans+=(n*(n+1))//2 -n 
  else:
   ans+=n
 print(ans) 

t=int(input())
for _ in range(t):
 s=list(input())
 n=len(s)
 ans=0
 c=0
 for i in range(0,n-1):
  if s[i]==s[i+1]:
   ans+=(n*(n+1))//2 -n 
  else:
   ans+=n
 print(ans) 

t=int(input())
for _ in range(t):
 s=input()
 n=len(s)
 k=0
 for i in range(1,len(s)):
  if s[i]==s[i-1]:
   k+=1
 ans=k*((n*(n+1))//2)
 for i in range(n):
  x=n-i
  if i==0:
   pass
  else:
   if s[i]==s[i-1]:
    ans-=x
   else:
    ans+=x
  x=i+1
  if i==n-1:
   pass
  else:
   if s[i+1]==s[i]:
    ans-=x
   else:
    ans+=x
 print(ans)
   


t=int(input())
for _ in range(t):
 s=input()
 k=0
 for i in range(1,len(s)):
  if s[i]==s[i-1]:
   k+=1
 ans=0
 for i in range(len(s)):
  for j in range(i,len(s)):
   ans+=k
   if i==0:
    pass
   else:
    if s[i-1]==s[i]:
     ans-=1
    else:
     ans+=1
   if j==len(s)-1:
    pass
   else:
    if s[j+1]==s[j]:
     ans-=1
    else:
     ans+=1
 print(ans)
   


for i in range(int(input())):
 ans=0
 str1=input()
 n=len(str1)
 for j in range(n-1):
  if str1[j]==str1[j+1]:
   ans+=((n*(n-1))//2)
  else:
   ans+=n
 print(ans) 
 


t = int(input())
for _ in range(t):
 s = input().strip()
 n = len(s)
 ans = 0
 for i in range(n - 1):
  if s[i] == s[i+1]:
   ans += (i + 1) * (n - i - 1) + i * (i + 1) // 2 + \
    (n - i - 2) * (n - i - 1) // 2
  else:
   ans += n
 print(ans)

a=int(input())
answer=[]
for i in range(a):
 s=input()
 l=len(s)
 ans=0
 for i in range(l-1):
  if s[i]==s[i+1]:
   ans=ans+((l-1)*l)/2
  elif s[i]!=s[i+1]:
   ans=ans+l
 answer.append(ans) 
for i in range(a):
 print(int(answer[i]))

a=int(input())
answer=[]
for i in range(a):
 s=input()
 l=len(s)
 ans=0
 for i in range(l-1):
  if s[i]==s[i+1]:
   ans=ans+((l-1)*l)/2
  elif s[i]!=s[i+1]:
   ans=ans+l
 answer.append(ans) 
for i in range(a):
 print(int(answer[i]))

# cook your dish here
def solve():
 t = int(input())
 for i in range(0, t):
  s = input()
  
  ans = 0
  
  sums = 0
  
  for k in range(0,len(s)-1):
   if s[k] == s[k+1]:
    sums += 1
  
  ans = len(s)*(len(s)+1)/2*sums
  
  for l in range(0, len(s)):
   for r in range(l, len(s)):
    if l>0:
     if s[l-1] == s[l]:
      ans -= 1
     else:
      ans += 1
    if r<len(s)-1:
     if s[r] == s[r+1]:
      ans -= 1
     else:
      ans += 1
  print(int(ans))
  
solve()