「Wdcfr-1」Magical Expression

给定一个合法的含 `|&?01` 的后缀表达式（以字符串形式给出，其为“合法的”代表将所有 `?` 替换为运算符后其会成为一个合法的后缀表达式），试求出其有多少个子串满足： - 将所有的 `?` 替换成 `|` 或 `&` 后，该串为合法的后缀表达式； - 存在一种将所有的 `?` 替换成 `|` 或 `&` 的方法使得该式所得结果为 $0$，同时也存在替换方法使得结果为 $1$。 请输出这样的子串的数量。两个子串是不同的仅当它们长度不同或位置不同。

Nitori is learning postfix expressions. She has a incomplete postfix expression $E$ of length $n$. Being a Youkai, she wants to find its magical property. Her postfix expression contains the Bitwise Or operator (denoted as `|`), the Bitwise And operator (denoted as `&`), and numbers `0` and `1`. Being incomplete, some operators have not been decided yet and are denoted as `?`. She promised that $E$ **will become a *vaild* postfix expression** after you complete it. In this problem, the term *substring* is defined as a continuous segment of $E$. **Two substrings are considered different as long as their positions or length differ.** So `1?0`, `01?0` are all substrings of `01?01?|` , but `0101` is not. Nitori found out that a substring of her expression is *magical* if and only if the following conditions are met: - It is possible to transform it into a *valid* postfix expression after replacing `?` with either `&` or `|` . - Among these transformations, it is possible to find at least one of them that after applying it, the expression yields $0$, and at least one of them that after applying it, the expression yields $1$. Your task is to find out the number of *magical* substrings.

The first line contains an integer $T$, the number of test cases. For each test case, input one integer $n$ and an expression $E$ in a single line.

For each test case, print one integer which is the answer.

2
3 01?
7 01?01?|

1
3

### Constraints $1\le T,n\le 2\times 10^6$. The sum of $n$ of all test cases $\le 2\times 10^6$.