You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the hard version of the problem. The only difference between the two versions is the constraint on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.

For a binary$$$^\dagger$$$ pattern $$$p$$$ and a binary string $$$q$$$, both of length $$$m$$$, $$$q$$$ is called $$$p$$$-good if for every $$$i$$$ ($$$1 \leq i \leq m$$$), there exist indices $$$l$$$ and $$$r$$$ such that:

- $$$1 \leq l \leq i \leq r \leq m$$$, and
- $$$p_i$$$ is a mode$$$^\ddagger$$$ of the string $$$q_l q_{l+1} \ldots q_{r}$$$.

For a pattern $$$p$$$, let $$$f(p)$$$ be the minimum possible number of $$$\mathtt{1}$$$s in a $$$p$$$-good binary string (of the same length as the pattern).

You are given a binary string $$$s$$$ of size $$$n$$$. Find $$$$$$\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).$$$$$$ In other words, you need to sum the values of $$$f$$$ over all $$$\frac{n(n+1)}{2}$$$ substrings of $$$s$$$.

$$$^\dagger$$$ A binary pattern is a string that only consists of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Character $$$c$$$ is a mode of string $$$t$$$ of length $$$m$$$ if the number of occurrences of $$$c$$$ in $$$t$$$ is at least $$$\lceil \frac{m}{2} \rceil$$$. For example, $$$\mathtt{0}$$$ is a mode of $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ is not a mode of $$$\mathtt{010}$$$, and both $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ are modes of $$$\mathtt{011010}$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the binary string $$$s$$$.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ consisting of only characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case, output the sum of values of $$$f$$$ over all substrings of $$$s$$$.

## Examples
```input
4
1
1
2
10
5
00000
20
11110110000000111111
```
```output
1
2
0
346
```

## Note
In the first test case, the only $$$\mathtt{1}$$$-good string is $$$\mathtt{1}$$$. Thus, $$$f(\mathtt{1})=1$$$.

In the second test case, $$$f(\mathtt{10})=1$$$ because $$$\mathtt{01}$$$ is $$$\mathtt{10}$$$-good, and $$$\mathtt{00}$$$ is not $$$\mathtt{10}$$$-good. Thus, the answer is $$$f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$$$.

In the third test case, $$$f$$$ equals to $$$0$$$ for all $$$1 \leq i \leq j \leq 5$$$. Thus, the answer is $$$0$$$.

Now solve the problem and return the code.