## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Paranoid String Codeforces Solution

B. Paranoid String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $\left[{T}_{2}{T}_{3}\right]$ 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 $\left(l,r\right)$ $1\le l\le r\le n$ such that $S\left[l\dots r\right]$ (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}_{1}{S}_{2}\dots {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 $\left(l,r\right)$ $1\le l\le r\le n$ such that $S\left[l\dots r\right]$ (the substring of $S$ from $l$ to $r$) is a paranoid string.