题目内容

对于一个字符串，小美每次操作可以:添加或者删除一个$0$字符或者$1$。

她定义一个字符串$t$的权值为:

满足任意次交换两个相邻字符的前提下使得任意相邻的两个字符都不相等的最少操作次数。

例如:对于$t=011$,其权值为$1$。

可以选择在$11$之间添加$0$变成$0101$。

也可以选择删除$1$变成$01$。

给你一个长度为$n$的字符串$s$，仅包含"$0、1$"，请你帮助小美求出非空子串的权值之和。

子串:是指一个字符串中的连续部分。

输入描述

第一行一个整数$t(1≤1≤10)$,表示数据组数。

对于每一组数据格式为:

第一行一个整数$n(1≤n≤2×10^5)$,表示字符串长度。

第二行第一个长度为n的字符串$s$，输入保证仅含"$0、1$".

单个测试文件数据保证$\sum n ≤2×10^5$。

输出描述

对于每一组数据：

每行输出一个整数，表示给定字符串的所有非空子串的权值之和。

样例1

输入

2
3
011
4
1111

输出

1
10

说明

对于第二个样例$s$="$1111$": 长度为$1$的子串$[1,1,1,1]$均不需要操作。 长度为$2$的子串$[11,11,11]$均需要操作一次，使得 $11→101$。 长度为$3$的子串$[111,111]$均需要操作两次，使得 $111→10101$。 长度为4的子串$[1111]$需要操作三次，使得 $1111→1010101$。

共累计$3×1+2×2+1×3=10$。