사라지는 문자열

0과 1로만 이루어진 문자열 $S$가 주어진다.

문자열에 다음 연산을 원하는 만큼 수행할 수 있다.

서로 인접한 같은 문자 두 개를 골라 동시에 지운다. 문자를 지운 뒤 남은 부분은 서로 붙는다.

어떤 문자열이 이 연산만으로 빈 문자열이 될 수 있으면 사라지는 문자열이라고 하자.

$1 \leq l \leq r \leq N$인 모든 정수쌍 $(l,r)$에 대해 부분문자열 $S_lS_{l+1}\cdots S_r$을 생각한다. 이들 중 사라지는 문자열인 부분문자열의 개수를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $S$

각 테스트 케이스마다 사라지는 부분문자열의 개수를 한 줄에 출력한다.

• $1 \leq T \leq 100$.
• $1 \leq N \leq 200\,000$.
• $S$의 길이는 $N$이다.
• $S$는 0과 1로만 이루어져 있다.
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.