Chef and Abhishek both are fighting for the post of Chairperson to be part of ACE committee and are trying their best. To select only one student their teacher gave them a binary string (string consisting of only 0's and 1's) and asked them to find number of sub-strings present in the given string that satisfy the following condition:
The substring should start with 0 and end with 1 or the substring should start with 1 and end with 0 but not start with 0 and end with 0 and start with 1 and end with 1.
More formally, strings such as 100,0101 are allowed since they start and end with different characters. But strings such as 0110,1101 are not allowed because they start and end with same characters.
Both Chef and Abhishek try their best to solve it but couldn't do it. You being a very good friend of Chef, he asks for your help so that he can solve it and become the Chairperson.

-----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 line of each test case contains a single integer N denoting the length of the string.
The second line of each test case contains a binary string of length N.

-----Output:-----
For each test case, print a single line containing one integer ― the number of sub strings satisfying above conditions.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq N \leq 10^9$
Binary string consist's only 0 and 1.

-----Sample Input:-----
1
4

1010

-----Sample Output:-----
4

-----EXPLANATION:-----
All possible substring are : { (1),(0),(1),(0),(10),(01),(10),(101),(010),(1010) }. Out of these only 4 substrings {(10),(01),(10),(1010)} start and end with different characters. Hence the answer 4.

Difficulty: interview

Starter code:

Solutions:
def countSubstr(str, n, x, y): 
  
    tot_count = 0
  
    count_x = 0
  
    for i in range(n):  
        if str[i] == x: 
            count_x += 1
        if str[i] == y: 
            tot_count += count_x 
    return tot_count 
  
t=int(input())
for _ in range(t):
    n=int(input())
    str=input()
    x='0'
    y='1'
    x1='1'
    y1='0'
    c1=countSubstr(str,n,x,y)
    c2=countSubstr(str,n,x1,y1)
    print(c1+c2)

# cook your dish here
for _ in range(int(input())):
    n=int(input())
    s=input()
    c=0
    count01=[[0,0] for _ in range(n)]
    for i in range(n-2,-1,-1):
        if s[i+1]=='1':
            count01[i][1]=count01[i+1][1]+1
            count01[i][0]=count01[i+1][0]
        else:
            count01[i][0]=count01[i+1][0]+1
            count01[i][1]=count01[i+1][1]
    for i in range(n):
        if s[i]=='1':
            c+=count01[i][0]
        else:
            c+=count01[i][1]
        # print("i=",i)
        # print(c)
        # print(count01)
    print(c)

for _ in range(int(input())):
    n=int(input())
    s=input()
    total=0
    zero=s.count("0")
    one=s.count("1")
    for i in range(n):
        if s[i]=="0":
            zero-=1
            total+=one
        else:
            one-=1
            total+=zero
    print(total)

t = int(input())
for o in range(t):
    n = int(input())
    p = str(input())
    l = list(p)
    one = l.count('1')
    zero = l.count('0')
    #print(one,zero)
    count = 0
    for i in range(n):
        if l[i] == '1':
            count+=zero
            one-=1
        else:
            count+=one 
            zero-=1 
    print(count)    

t=int(input())
for j in range(t):

    n=int(input())
    s=input()

    count1=0
    count2=0
    for i in range(len(s)):
        if s[i]=='1':
            count1+=1
    for i in range(len(s)):
        if s[i]=='0':
            count2+=1
    # print(count1,count2)
    print(count1*count2)

# cook your dish here
for ad in range(int(input())):
    n=int(input())
    s=list(input())
    zero=s.count("0")
    one=s.count("1")
    l=s
    ans=0
    for i in range(n):
        if l[i]=="0":
            zero-=1
            ans+=one
        else:
            one-=1
            ans+=zero
    print(ans)

for _ in range(int(input())):
    
    n = int(input())
    s = input()
    # count = 0
    
    # for i else:
            
    #         for j in range(i+1,n):
    #             if s[j] == "1":
    #                 count+=1in range(0,n):
        
    #     if s[i] == '1':
            
    #         for j in range(i+1,n):
                
    #             if s[j] == '0':
    #                 count+=1
        
    print(s.count('0')*s.count('1'))


for _ in range(int(input())):
    
    n = int(input())
    s = input()
    # count = 0
    
    # for i else:
            
    #         for j in range(i+1,n):
    #             if s[j] == "1":
    #                 count+=1in range(0,n):
        
    #     if s[i] == '1':
            
    #         for j in range(i+1,n):
                
    #             if s[j] == '0':
    #                 count+=1
        
    print(s.count('0')*s.count('1'))


def fac(x):
    x=len(x)
    return int(((x-1)*(x))/2)


t= int(input())
for o in range(t):
    n=int(input())
    s=input()
    a=s.split("1")
    a="".join(a)
    b=s.split("0")
    b="".join(b)
    print(fac(s)-fac(a)-fac(b),)

for t in range(int(input())):
    def csbstr(str,n,a,b):
        tot,c=0,0
        for i in range(n):
            if(str[i]==a):
                c+=1
            if(str[i]==b):
                tot+=c
        return tot

    n=int(input())
    str=input()
    count1=csbstr(str,n,"1","0")
    count2=csbstr(str,n,"0","1")
    print(count1+count2)

# cook your dish here
def fac(x):
    x=len(x)
    return int(((x-1)*(x))/2)


t= int(input())
for o in range(t):
    n=int(input())
    s=input()
    a=s.split("1")
    a="".join(a)
    b=s.split("0")
    b="".join(b)
    print(fac(s)-fac(a)-fac(b),)


for x in range(int(input())):
    l=int(input())
    s=input()
    z=0
    for x in s:
        if x=='0':
            z+=1
    print(z*(l-z))        



def fac(x):
    x=len(x)
    return int(((x-1)*(x))/2)


t= int(input())
for o in range(t):
    n=int(input())
    s=input()
    a=s.split("1")
    a="".join(a)
    b=s.split("0")
    b="".join(b)
    print(fac(s)-fac(a)-fac(b),)


# cook your dish here
for _ in range(int(input())):
    N = int(input())
    l = input()
    arr1 = []
    arr2 = []
    #total = sum(arr1)
    #print(total)
    count1 = 0
    count2 = 0
    for i in range(len(l)-1, -1, -1):
        if(l[i] == '0'):
            arr1.append(count1)
            count2+=1
        elif(l[i] == '1'):
            count1+=1
            arr2.append(count2)
    print(sum(arr1)+sum(arr2))

for _ in range(int(input())):
    N = int(input())
    binstr = input()
    a = binstr.count('1')
    b = binstr.count('0')
    print(a*b)

for _ in range(int(input())):
    N = int(input())
    binstr = input()
    print(binstr.count('1')*binstr.count('0'))

testcase=int(input())
while(testcase!=0):
    testcase-=1
    n=int(input())
    l=input()
    print(l.count('1')*l.count('0'))

for _ in range(int(input())):N = int(input());binstr = input();print(binstr.count('1')*binstr.count('0'))

# def countSubStr(st,n):
# 	res = 0
# 	for i in range(0,n):
# 		if (st[i] == '1'):
# 			for j in range(i+1, n) :
# 				if (st[j] == '0'):
# 					res += 1
# 		if (st[i] == '0'):
# 			for j in range(i+1, n):
# 				if(st[j] == '1'):
# 					res += 1
# 	return res 
# for _ in range(int(input())):
# 	N = int(input());binstr = input()
# 	#for any N, number of contigious subarrays will be sum of all i in range(1,N + 1)
# 	print(countSubStr(list(binstr),N),end="") #TLE (obviously, since it's O(N**2))
for _ in range(int(input())):
	N = int(input());binstr = input()
	print(binstr.count('1')*binstr.count('0'))

for _ in range(int(input())):
    n = int(input())
    arr = input()
    ans = 0
    
    print(arr.count("1")*arr.count("0"))
    # for i in range(0, n-1):
    #     if arr[i] == "1":
    #         ans += arr[i+1:].count("0")
    #     else:
    #         ans += arr[i+1:].count("1")
    # print(ans)


from functools import lru_cache
import sys
try:
    from cp import input
except:
    def input():
        return sys.stdin.readline()
try:
    import numpy as np
except:
    pass
import math
import copy
import random
from copy import deepcopy
# def input(): return sys.stdin.readline()
def itarr(arr): return list(range(len(arr)))
def mp(): return list(map(int, input().split()))
def lmp(): return list(map(int, input().strip().split()))
def inp(): return int(input())


MOD = 1000000007


sys.setrecursionlimit(100000)
sys.settrace
inf_p = float('inf')
inf_n = float('-inf')

dsu=[]

def find(n):
    if n==dsu[n]:
        return n
    tmp=find(dsu[n])
    dsu[n]=tmp
    return tmp

def union(a,b):
    a=find(a)
    b=find(b)
    if a!=b:
        dsu[b]=a

adj=[]
vis=[]
wt=[]
MAXE=0
MAXO=0
ans=0

def even_parity(n):
    return (bin(n)[2:].count('1')%2)==0
def odd_parity(n):
    return not even_parity(n)

def dfse(curr_node,p):
    nonlocal MAXE, MAXO,vis,ans

    for node in adj[curr_node]:
        if vis[node]==0 :
            if even_parity(wt[node-1]):
                dfs(node,num)
        
def dfso(curr_node,p):
    nonlocal MAXE, MAXO,vis,ans
    
    for node in adj[curr_node]:
        if vis[node]==0 :
            if odd_parity(wt[node-1]):
                dfs(node,num)

def main():
    n=inp()
    s=input().strip()
    if len(s)==0:
        s=input().strip
    ones=[0]* (n+1)
    zeros=[0]* (n+1)
    one =0 
    zero=0
    for i in range(len(s)):
        ones[i]=one
        zeros[i]=zero
        if s[i]=='1':
            one+=1
        else:
            zero+=1 
    tot=0
    # print(ones,zeros)
    for i in range(n-1,0,-1):
        if s[i]=='1':
            tot+=zeros[i]
        else:
            tot+=ones[i]
        # print(i)
    print(tot)

# main()
for i in range(inp()):
    main()
# cook your dish here


#Coded By Ujjwal Bharti
tulu = int(input())
for _ in range(tulu):
    n = int(input())
    string = input()
    flag = False
    counter = 0
    frequency = 1
    for i in string:
        if i == "0" and flag==False:
            flag=True
            continue
        if flag and i == "0":
            frequency += 1
        if flag and i == "1":
            counter += (frequency)
    flag = False
    frequency = 1
    for i in string:
        if i == "1" and flag==False:
            flag=True
            continue
        #print(frequency)
        if flag and i=="1":
            frequency += 1
        if flag and i == "0":
            counter += frequency
    print(counter)

n = int(input())

while n>0:
    l = int(input())
    s = input()
    zero = 0
    one = 0
    subs = 0
    for i in range(l):
        if s[i]=='0':
            zero+=1
        else:
            one+=1
    subs=one*zero
    print(subs)

    n-=1