B'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 <= q i <= q m ), there exist indices l and r such that: 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} . Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 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 <= n <= 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 . For each test case, output the sum of values of f over all substrings of s . In the first te'...