There is an integer sequence of length $$$n$$$, denoted as $$$a_1,a_2,\cdots,a_n$$$, where the integers in the sequence can only be $$$0$$$ or $$$1$$$, but some positions in the sequence have not yet been determined.
Now you want to fill the undetermined positions in the sequence with $$$0$$$ or $$$1$$$ in such a way that the number of inversion pairs is maximized.
The number of inversion pairs in a sequence $$$a_1,a_2,\cdots,a_n$$$ is defined as the number of integer pairs $$$(i,j)$$$ such that $$$1\leq i \lt j\leq n$$$ and $$$a_i \gt a_j$$$.
The first line contains a positive integer $$$T$$$ $$$(1\leq T\leq 10^4)$$$, indicating the number of test cases.
For each test case, the first line contains an integer $$$n$$$ $$$(2\leq n\leq 10^6)$$$, representing the length of the sequence.
The second line contains a string $$$s$$$ of length $$$n$$$ consisting only of 0, 1, and ?, representing the sequence, where the $$$i$$$-th character $$$s_i$$$ being ? indicates that $$$a_i$$$ is unknown and needs to be filled in, otherwise it represents $$$a_i$$$.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\times 10^6$$$.
For each test case, output a single integer on a new line, representing the maximum number of inversion pairs.
4311031?04????71?0?0?1
2 2 4 8
For the first sample case, the number of inversion pairs in 110 is $$$2$$$.
For the second sample case, it can be filled as 100 or 110, both yielding $$$2$$$ inversion pairs.
For the third sample case, it can be filled as 1100, resulting in $$$4$$$ inversion pairs.
For the fourth sample case, it can be filled as 1100001 or 1101001, both yielding $$$8$$$ inversion pairs.
