D2. Sum over all Substrings (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

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

Example
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$$$.