codeforces#P1930D2. Sum over all Substrings (Hard Version)

Sum over all Substrings (Hard Version)

Description

This is the hard version of the problem. The only difference between the two versions is the constraint on tt and nn. You can make hacks only if both versions of the problem are solved.

For a binary^\dagger pattern pp and a binary string qq, both of length mm, qq is called pp-good if for every ii (1im1 \leq i \leq m), there exist indices ll and rr such that:

  • 1lirm1 \leq l \leq i \leq r \leq m, and
  • pip_i is a mode^\ddagger of the string qlql+1qrq_l q_{l+1} \ldots q_{r}.

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

You are given a binary string ss of size nn. Find i=1nj=inf(sisi+1sj).\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 ff over all n(n+1)2\frac{n(n+1)}{2} substrings of ss.

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

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

Each test contains multiple test cases. The first line contains the number of test cases tt (1t1051 \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 nn (1n1061 \le n \le 10^6) — the length of the binary string ss.

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

It is guaranteed that the sum of nn over all test cases does not exceed 10610^6.

For each test case, output the sum of values of ff over all substrings of ss.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t1051 \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 nn (1n1061 \le n \le 10^6) — the length of the binary string ss.

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

It is guaranteed that the sum of nn over all test cases does not exceed 10610^6.

Output

For each test case, output the sum of values of ff over all substrings of ss.

输入数据 1

4
1
1
2
10
5
00000
20
11110110000000111111

输出数据 1

1
2
0
346

Note

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

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

In the third test case, ff equals to 00 for all 1ij51 \leq i \leq j \leq 5. Thus, the answer is 00.