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

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)


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


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


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


for _ in range(int(input())):
	N = int(input())
	l = input()
	arr1 = []
	arr2 = []
	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)


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())
	arr = input()
	ans = 0
	print(arr.count('1') * arr.count('0'))


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 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
	for i in range(n - 1, 0, -1):
		if s[i] == '1':
			tot += zeros[i]
		else:
			tot += ones[i]
	print(tot)
for i in range(inp()):
	main()


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