Let's call a binary string $T$ of length $m$ indexed from $1$ to $m$ paranoid if we can obtain a string of length $1$ by performing the following two kinds of operations $m-1$ times in any order :

Select any substring of $T$ that is equal to 01, and then replace it with 1.

Select any substring of $T$ that is equal to 10, and then replace it with 0.

For example, if $T = $ 001, we can select the substring $[T_2T_3]$ and perform the first operation. So we obtain $T = $ 01.

You are given a binary string $S$ of length $n$ indexed from $1$ to $n$. Find the number of pairs of integers $(l, r)$ $1 \le l \le r \le n$ such that $S[l \ldots r]$ (the substring of $S$ from $l$ to $r$) is a paranoid string.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of $S$.

The second line of each test case contains a binary string $S$ of $n$ characters $S_1S_2 \ldots S_n$. ($S_i = $ 0 or $S_i = $ 1 for each $1 \le i \le n$)

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output the number of pairs of integers $(l, r)$ $1 \le l \le r \le n$ such that $S[l \ldots r]$ (the substring of $S$ from $l$ to $r$) is a paranoid string.


-----Examples-----

Input
5
1
1
2
01
3
100
4
1001
5
11111
Output
1
3
4
8
5


-----Note-----

In the first sample, $S$ already has length $1$ and doesn't need any operations.

In the second sample, all substrings of $S$ are paranoid. For the entire string, it's enough to perform the first operation.

In the third sample, all substrings of $S$ are paranoid except $[S_2S_3]$, because we can't perform any operations on it, and $[S_1S_2S_3]$ (the entire string).

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = input().strip()
	ans = n
	for i in range(1, n):
		if s[i - 1] != s[i]:
			ans += i
	return ans
for _ in range(int(input())):
	print(solve())


import sys

def run():
	size = int(input())
	s = input()
	count = len(s)
	prevc = s[0]
	for (i, c) in enumerate(s[1:], 1):
		if prevc != c:
			count += i
		prevc = c
	print(count)
t = int(input())
for _ in range(t):
	run()


def solve():
	n = int(input())
	s = input()
	last = ' '
	now = ans = 0
	for i in s[::-1]:
		if i != last:
			now += 1
		last = i
		ans += now
	print(ans)
T = int(input())
for _ in range(T):
	solve()


def func():
	n = int(input())
	s = input('')
	ans = n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans += i
	print(ans)
t = int(input())
for _ in range(t):
	func()


import io, os, math

def ri():
	return int(input().strip())

def rl():
	return list(map(int, input().strip().split()))

def Solve():
	n = ri()
	s = input().strip()
	(last, cnt) = ('', 0)
	ans = n * (n - 1) // 2 + n
	for i in range(n):
		if s[i] != last:
			(last, cnt) = (s[i], 1)
		else:
			cnt += 1
			ans -= i
	print(ans)
T = ri()
while T:
	T -= 1
	Solve()


def test():
	n = int(input())
	s = input()
	par = n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			par += i
	print(par)
t = int(input())
for i in range(t):
	test()


def solve():
	n = int(input())
	s = input()
	ans = n * (n + 1) // 2
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ans -= i
	print(ans)
t = int(input())
for i in range(t):
	solve()


def func():
	n = int(input())
	s = input()
	count = 1
	stack = [s[0]]
	for i in range(1, n):
		if s[i] == s[i - 1]:
			count += 1
		else:
			count += i + 1
	print(count)
tc = int(input())
while tc > 0:
	func()
	tc -= 1


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	s = input()
	count = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			count += i + 1
		else:
			count += 1
	print(count)
t = int(input())
while t != 0:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	print(n + sum((i for i in range(1, n) if s[i] != s[i - 1])))


for _ in range(int(input())):
	n = int(input())
	a = input()
	c = n
	for i in range(1, n):
		if a[i] != a[i - 1]:
			c += i
	print(c)


def paranoidString(n, s):
	ans = n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans += i
	return ans
travel = int(input())
for i in range(travel):
	n = int(input())
	s = input()
	print(paranoidString(n, s))


def solve(n, S):
	total = n
	for r in range(1, n):
		if S[r - 1] != S[r]:
			total += r
	return total
t = int(input())
for _ in range(t):
	n = int(input())
	S = input()
	print(solve(n, S))


import collections
import math
import sys
from queue import PriorityQueue
from random import randint

def main(testnumber):
	n = int(input())
	s = input()
	ans = n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans += i
	print(ans)
t = int(input())
cnt = 1
while t > 0:
	main(cnt)
	cnt += 1
	t -= 1


def main():
	l = int(input())
	s = input()
	ans = l
	for i in range(1, l):
		if s[i] == s[i - 1]:
			continue
		ans += i
	print(ans)
for _ in range(int(input())):
	main()


def ss(s):
	n = len(s)
	ans = n
	for i in range(1, n):
		if s[i] == '1':
			if s[i - 1] == '0':
				ans += i
		elif s[i - 1] == '1':
			ans += i
	return ans
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	print(ss(s))


import sys
input = lambda : sys.stdin.readline().strip()

def new_func(input):
	for _ in ' ' * int(input()):
		n = int(input())
		a = input()
		count = 1
		for i in range(1, n):
			if a[i] != a[i - 1]:
				count += i + 1
			else:
				count += 1
		print(count)
new_func(input)


def solve():
	n = int(input())
	ans = int()
	s = input()
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans += i
	print(ans + n)
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans += i
	print(ans + n)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = n
	for x in range(1, n):
		if s[x] != s[x - 1]:
			ans += x
	print(ans)


def paranoidString(n, s):
	ans = n
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			if i != 0 and s[i - 1] == '0':
				ans += i
		elif i > 0 and s[i - 1] == '1':
			ans += i
	return ans
travel = int(input())
for i in range(travel):
	n = int(input())
	s = input()
	print(paranoidString(n, s))


n = int(input())
while n:
	x = int(input())
	y = input()
	z = x
	for j in range(1, x):
		if y[j] != y[j - 1]:
			z += j
	print(z)
	n -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	S = input().strip()
	tot = n
	for i in range(1, n):
		if S[i] != S[i - 1]:
			tot += i
	print(tot)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans += i
	ans += n
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	if s.count('0') == 0 or s.count('0') == n:
		print(n)
	else:
		ans = 0
		for i in range(1, n):
			if s[i] != s[i - 1]:
				ans += i
		print(ans + n)


n = int(input())
for i in range(n):
	a = int(input())
	b = input()
	total = a * (a + 1) / 2
	for j in range(len(b) - 1):
		if b[j] == b[j + 1]:
			total = total - j - 1
	print(int(total))


n = int(input())
l = []
for i in range(n):
	t = int(input())
	s = input()
	l.append(s)
for i in l:
	t = len(i)
	s = int(t * (t + 1) / 2)
	for j in range(len(i) - 1):
		if i[j] == i[j + 1]:
			s = s - (j + 1)
	print(s)


for i in range(int(input())):
	size = int(input())
	s = input()
	res = len(s)
	for i in range(1, size):
		if s[i - 1] != s[i]:
			res += i
	print(res)


from collections import Counter, deque
from collections import OrderedDict
import math
from random import randint
from bisect import bisect
import sys
import re
MOD = 10 ** 9 + 7
MAX = sys.maxsize
MIN = -sys.maxsize

class get:

	def int():
		return list(map(int, input().split()))

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

	def map():
		return map(int, input().split())

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve():
	n = int(input())
	s = input()
	for i in range(1, n):
		if s[i] != s[i - 1]:
			n += i
	print(n)
t = int(input())
for tt in range(t):
	solve()


import math

def fun(nums):
	c = len(nums)
	for i in range(1, len(nums)):
		if nums[i] != nums[i - 1]:
			c += i
	return c
n = int(input())
for _ in range(n):
	_ = input()
	arr = input()
	arr = list(arr)
	arr = list(map(int, arr))
	print(fun(arr))


for _ in range(int(input())):
	ls = int(input())
	out = ls
	s = input()
	for i in range(1, ls):
		if s[i] != s[i - 1]:
			out += i
	print(out)


def solve():
	n = int(input())
	s = input()
	total = n
	for i in range(1, n):
		total = total + i
	for i in range(1, n):
		if s[i] == s[i - 1]:
			total -= i
	print(total)
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	s = input()
	res = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			res += 1
		else:
			res += i + 1
	print(res + 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			cnt += i
	print(cnt + n)


t = int(input())
while t:
	l = int(input())
	s = input()
	ans = l
	for i in range(1, l):
		if s[i - 1] != s[i]:
			ans = ans + i
	print(ans)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	f = input()
	for j in range(1, len(f)):
		if f[j - 1] != f[j]:
			n += j
	print(n)


for i in range(int(input())):
	n = int(input())
	s = str(input())
	anuvab = n
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			anuvab = anuvab + i
	print(anuvab)


for _ in range(int(input())):
	a = int(input())
	s = list(input())
	ans = a
	for i in range(1, a):
		if s[i] != s[i - 1]:
			ans += i
	print(ans)


t = int(input())
while t:
	n = int(input())
	s = input()
	res = n
	for i in range(1, n):
		if s[i - 1] != s[i]:
			res += i
	print(res)
	t -= 1


from itertools import accumulate

def fuck(s) -> int:
	return 1 + sum([1 + i * (s[i] != s[i - 1]) for i in range(1, n)])
T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	print(fuck(s))


for i in range(int(input())):
	a = int(input())
	s = input()
	ans = 1
	for i in range(1, a):
		if s[i] != s[i - 1]:
			ans += i + 1
		else:
			ans += 1
	print(ans)


a = int(input())
for i in range(a):
	b = int(input())
	c = input()
	d = b
	for j in range(1, b):
		if c[j] != c[j - 1]:
			d += j
	print(d)


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = a * (a + 1) // 2
	for i in range(1, a):
		if b[i] == b[i - 1]:
			c -= i
	print(c)


t = int(input())
while t:
	a = int(input())
	b = input()
	c = a
	for i in range(1, a):
		if b[i] != b[i - 1]:
			c += i
	print(c)
	t -= 1


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
	n = int(input())
	arr = get_string()
	ans = n
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			ans += i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	if n > 1:
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				ans += i + 1
		total = int(n * (n + 1) / 2)
		print(total - ans)
	else:
		print(1)


T = int(input())
for i in range(0, T):
	n = int(input())
	s = input()
	ans = 0
	for i in range(0, n):
		if s[i] != s[i - 1]:
			ans += i
	print(ans + n)


t = int(input())
for i in range(t):
	tc = int(input())
	inp = input()
	cnt = tc
	for j in range(1, tc):
		if inp[j] != inp[j - 1]:
			cnt += j
	print(cnt)


for i in range(int(input())):
	n = int(input())
	s = input()
	sum = 1
	for j in range(1, n):
		if s[j - 1] == s[j]:
			sum += 1
		else:
			sum += j + 1
	print(sum)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	k = 0
	for i in range(n - 1, 0, -1):
		if s[i] != s[i - 1]:
			k += i
	print(k + n)


T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	res = n * (n + 1) // 2
	for i in range(1, n):
		if s[i - 1] == s[i]:
			res -= i
	print(res)


for _ in range(int(input())):
	n = int(input())
	string = input()
	ans = n
	for i in range(1, n):
		if string[i] != string[i - 1]:
			ans += i
	print(ans)


inp1 = int(input())
for i in range(inp1):
	inp2 = int(input())
	inp3 = input()
	subarr = inp2 * (inp2 + 1) // 2
	for i in range(inp2):
		if inp3[i] == inp3[i - 1]:
			subarr -= i
	print(subarr)


for i in range(int(input())):
	n = int(input())
	x = input()
	for i in range(1, len(x)):
		if x[i] != x[i - 1]:
			n += i
	print(n)


for t in range(int(input())):
	n = int(input())
	s = input()
	p = n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			p += i
	print(p)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = n
	for idx in range(1, n):
		if s[idx - 1] != s[idx]:
			ans += idx
	print(ans)


x = int(input())
for i in range(x):
	l = int(input())
	A = input()
	total = l
	for j in range(1, l):
		if A[j - 1] != A[j]:
			total = total + j
	print(total)


for i in range(int(input())):
	number = int(input())
	a = input()
	for i in range(1, len(a)):
		if a[i] != a[i - 1]:
			number += i
	print(number)


for _ in range(int(input())):
	input()
	s = input()
	ans = len(s)
	for i in range(1, len(s)):
		if s[i - 1] != s[i]:
			ans += i
	print(ans)


t = int(input())
for i in range(t):
	length = int(input())
	s = input()
	ans = length
	for i in range(2, length):
		if s[i] != s[i - 1]:
			ans += i
	if length >= 2:
		if s[0] != s[1]:
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c = n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			c += i
	print(c)


ans = []
for i in range(int(input())):
	n = int(input())
	s = str(input())
	x = n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			x += i
	ans.append(x)
for i in ans:
	print(i)


for t in range(int(input())):
	n = int(input())
	s = input()
	ans = n
	for i in range(1, len(s)):
		if s[i - 1] != s[i]:
			ans += i
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input())
	prev = s[0]
	for (j, c) in enumerate(s[1:]):
		if c != prev:
			prev = c
			n += j + 1
	print(n)


for _ in range(int(input())):
	x = input()
	y = input()
	answer = int(x)
	for i in range(1, int(x)):
		if y[i] == y[i - 1]:
			pass
		else:
			answer += i
	print(answer)


a = int(input())
for i in range(a):
	b = int(input())
	c = input()
	if b == 1:
		print(1)
	else:
		ans = b
		for j in range(1, len(c)):
			if c[j] != c[j - 1]:
				ans += j
		print(ans)


import bisect
xx = int(input())
for jj in range(xx):
	n = int(input())
	a = input()
	ans = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			ans += i + 1
		else:
			ans += 1
	print(ans)


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	cnt = n
	for r in range(1, n):
		if s[r] != s[r - 1]:
			cnt += r
	print(cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print(1)
		continue
	ans = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			ans += i + 1
	a = (n + 1) * n // 2
	print(a - ans)


t = int(input())
result = []
for i in range(t):
	n = int(input())
	s = input()
	nbpairs = n
	for j in range(1, n):
		if s[j] != s[j - 1]:
			nbpairs += j
	result.append(nbpairs)
for i in result:
	print(i)


def paranoid(s, n):
	if n == 1:
		return 1
	else:
		ans = n
		i = n - 1
		while i > 0:
			if s[i] == '0' and s[i - 1] == '1' or (s[i] == '1' and s[i - 1] == '0'):
				ans += i
			i -= 1
		return ans
tests = int(input())
for _ in range(tests):
	n = int(input())
	s = input()
	print(paranoid(s, n))


t = int(input())
for _ in range(t):
	m = int(input())
	s = input()
	ans = m
	for i in range(1, m):
		if s[i] != s[i - 1]:
			ans += i
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = input()
	p = '1'
	ans = 0
	for (i, x) in enumerate(s):
		if x == p:
			ans += 1
		else:
			ans += i + 1
		p = x
	print(ans)


import sys

def read(type):
	return type(sys.stdin.readline().strip())
for _ in range(read(int)):
	n = read(int)
	s = read(str)
	res = n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			res += i
	print(res)